พิมพ์ Safe Primes ทั้งหมดต่ำกว่า N ใน C++

ในปัญหานี้ เราจะได้รับจำนวนเต็ม N และต้องพิมพ์ Safe Prime Numbers ทั้งหมดที่มีค่าน้อยกว่า N

Safe Prime Number คือจำนวนเฉพาะที่สามารถแสดงได้ในรูป [(2 × p) + 1] โดยที่ p ก็เป็นจำนวนเฉพาะเช่นกัน

ตัวอย่าง - 5[(2×2)+1], 7[(2×3)+1]

ตัวอย่างเพื่อความเข้าใจ

Input: N = 12
Output: 5 7 11

เพื่อแก้ปัญหานี้ เราจะหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า N (โดยใช้ Sieve of Eratosthenes) และตรวจสอบว่าจำนวนเฉพาะนั้นเป็น Safe Prime หรือไม่ และพิมพ์ถ้าเป็น Safe Prime

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

void printPrime(int n) {
    cout << n << "\t";
}

void generateSafePrimes(int n) {
    int prime[n + 1];
    for (int i = 2; i <= n; i++)
        prime[i] = 1;
    prime[0] = prime[1] = 0;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == 1) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = 0;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (prime[i] != 0) {
            int temp = (2 * i) + 1;
            if (temp <= n && prime[temp] != 0)
                prime[temp] = 2;
        }
    }
    for (int i = 5; i <= n; i++)
        if (prime[i] == 2)
            printPrime(i);
}

// Driver code
int main() {
    int n = 34;
    cout << "Safe Prime numbers less than " << n << " are :\n";
    generateSafePrimes(n);
    return 0;
}

ผลลัพธ์

Safe Prime numbers less than 34 are -

5 7 11 23