เลขซูเปอร์ไพรม์ (Super Prime) ในภาษา C

เลขซูเปอร์ไพรม์ (Super Prime) คือจำนวนเฉพาะที่อยู่ในตำแหน่งที่เป็นจำนวนเฉพาะในลำดับของจำนวนเฉพาะทั้งหมด เรียกอีกอย่างว่า "High-order primes" ตัวอย่างเช่น 3, 5, 11, 17, ...

ตัวอย่าง

Input: 13

Output: 3, 5, 11

อธิบาย: จำนวนเฉพาะน้อยกว่า 13 คือ 2, 3, 5, 7, 11, 13 ตำแหน่งที่เป็นจำนวนเฉพาะคือ 2, 3, 5, 7, 11, 13 ดังนั้น จำนวนเฉพาะตัวที่ 2 คือ 3, ตัวที่ 3 คือ 5, ตัวที่ 5 คือ 11 → เป็นซูเปอร์ไพรม์

โค้ดตัวอย่าง (C++)

#include <iostream>
using namespace std;

bool sieveOfEratosthenes(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];
    sieveOfEratosthenes(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;
}

ผลลัพธ์

Super-Primes less than 343 are: 3 5 11 17 31 41 59 67 83 109 127 157 179 191 211 241 277 283 331