Số siêu nguyên tố (Super Prime) trong C

Số siêu nguyên tố là số nguyên tố nằm ở vị trí là số nguyên tố trong dãy các số nguyên tố. Ví dụ: 3, 5, 11, 17...

Ví dụ: Tìm siêu nguyên tố < 13

Các số nguyên tố < 13: 2, 3, 5, 7, 11, 13

• Vị trí 2 (số nguyên tố) → 3 là siêu nguyên tố
• Vị trí 3 (số nguyên tố) → 5 là siêu nguyên tố
• Vị trí 5 (số nguyên tố) → 11 là siêu nguyên tố

Kết quả: 3, 5, 11

Thuật toán

1. Dùng sàng Eratosthenes tìm tất cả số nguyên tố ≤ n
2. Lưu vào mảng primes[]
3. In primes[k] nếu (k+1) là số nguyên tố

Chương trình

#include <iostream>
using namespace std;

void sieve(int n, bool isPrime[]) {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) isPrime[i] = true;
    for (int p = 2; p * p <= n; p++)
        if (isPrime[p])
            for (int i = p * 2; i <= n; i += p)
                isPrime[i] = false;
}

void superPrimes(int n) {
    bool isPrime[n + 1];
    sieve(n, isPrime);
    
    int primes[n + 1], j = 0;
    for (int p = 2; p <= n; p++)
        if (isPrime[p]) primes[j++] = p;
    
    for (int k = 0; k < j; k++)
        if (isPrime[k + 1])
            cout << primes[k] << " ";
}

int main() {
    int n = 343;
    cout << "Super-Primes less than " << n << " are:\n";
    superPrimes(n);
    return 0;
}

Kết quả

3 5 11 17 31 41 59 67 83 109 127 157 179 191 211 241 277 283 331