Số siêu nguyên tố (Đề thi Tin học trẻ)

def is_prime(n):
    """Kiểm tra n có phải là số nguyên tố hay không"""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_super_primes(n, current, result):
    """Tìm số siêu nguyên tố với N chữ số"""
    if n == 0:
        # Kiểm tra nếu số hiện tại là số nguyên tố
        if is_prime(current):
            result.append(current)
    else:
        # Duyệt qua các chữ số từ 1 đến 9
        for i in range(1, 10):
            # Nối chữ số vào cuối số hiện tại
            next_number = current * 10 + i
            # Đệ quy để tìm các số siêu nguyên tố có N chữ số
            generate_super_primes(n - 1, next_number, result)

def find_super_primes_with_n_digits(n):
    """Tìm số siêu nguyên tố với N chữ số"""
    result = []
    generate_super_primes(n, 0, result)
    return result

# Nhập dữ liệu vào là số nguyên N
N = int(input("Nhập số nguyên N (0 < N < 10): "))
if N > 0 and N < 10:
    super_primes = find_super_primes_with_n_digits(N)
    print(f"Có {len(super_primes)} số siêu nguyên tố có {N} chữ số:")
    print(super_primes)
else:
    print("Số N không hợp lệ!")

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

// Hàm kiểm tra số nguyên tố
bool isPrime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

// Hàm kiểm tra số siêu nguyên tố
bool isSuperPrime(int n, int original, int count) {
    if (n <= 1)
        return false;
    if (!isPrime(n))
        return false;
    if (original != n && count == 0)
        return true;
    int digit = log10(n) + 1;
    int newCount = count;
    while (n > 0) {
        newCount--;
        n /= 10;
    }
    if (newCount > 0)
        return false;
    return isSuperPrime(original % int(pow(10, digit - 1)), original, count - 1);
}

// Hàm đệ quy để tìm số siêu nguyên tố
void findSuperPrime(int n, int original, int count) {
    if (n <= 0)
        return;
    findSuperPrime(n - 1, original, count);
    if (isSuperPrime(n, n, count))
        cout << n << " ";
}

int main() {
    int n;
    cout << "Nhap vao so nguyen duong n (0 < n < 10): ";
    cin >> n;
    cout << "Cac so sieu nguyen to co " << n << " chu so la: ";
    findSuperPrime(pow(10, n) - 1, pow(10, n) - 1, n - 1);
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Hàm kiểm tra số nguyên tố
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// Hàm kiểm tra số siêu nguyên tố
bool isSuperPrime(int n) {
    if (!isPrime(n)) {
        return false;
    }
    int len = to_string(n).length();
    for (int i = 1; i < len; i++) {
        int p = n / pow(10, i);
        if (!isPrime(p)) {
            return false;
        }
    }
    return true;
}

// Hàm tìm các số siêu nguyên tố có N chữ số
vector<int> findSuperPrimes(int N) {
    vector<int> superPrimes;
    int start = pow(10, N - 1);
    int end = pow(10, N);
    for (int i = start; i < end; i++) {
        if (isSuperPrime(i)) {
            superPrimes.push_back(i);
        }
    }
    return superPrimes;
}

// Hàm main
int main() {
    int N;
    cout << "Nhap vao so N: ";
    cin >> N;
    vector<int> superPrimes = findSuperPrimes(N);
    cout << "Cac so sieu nguyen to co " << N << " chu so la: " << endl;
    for (int i = 0; i < superPrimes.size(); i++) {
        cout << superPrimes[i] << " ";
    }
    cout << endl;
    return 0;
}

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def is_super_prime(n):
    if not is_prime(n):
        return False
    while n > 0:
        n //= 10
        if not is_prime(n):
            return False
    return True

def find_super_primes(n):
    primes = []
    sieve = [True] * (10 ** n)
    sieve[0] = sieve[1] = False
    for i in range(2, int(10 ** (n / 2)) + 1):
        if sieve[i]:
            for j in range(i * i, 10 ** n, i):
                sieve[j] = False
    for k in range(10 ** (n - 1), 10 ** n):
        if sieve[k] and is_super_prime(k):
            primes.append(k)
    return primes

n = int(input("Enter the number of digits: "))
super_primes = find_super_primes(n)
print(f"There are {len(super_primes)} super primes with {n} digits:")
for prime in super_primes:
    print(prime)