In tất cả các số nguyên tố an toàn dưới N trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên N và chúng ta phải in ra tất cả số nguyên tố an toàn có giá trị nhỏ hơn N.

Một số nguyên tố an toàn là một số nguyên tố có thể được biểu diễn dưới dạng [(2 * p) - 1] trong đó p cũng là một số nguyên tố.

Ví dụ - 5 [(2 * 2) +1], 7 [(2 * 3) +1].

Hãy lấy một vài ví dụ để hiểu rõ hơn vấn đề -

Input: N = 12
Output: 5 7 11.

Để giải quyết vấn đề này, chúng ta sẽ tìm tất cả các số nguyên tố nhỏ hơn N (đối với điều này, chúng ta sẽ sử dụng Sieve of Eratosthenes). Và kiểm tra xem số nguyên tố có phải là số nguyên tố an toàn hay không và in ra xem nó có phải là số nguyên tố an toàn hay không.

Ví dụ

#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;
}

Đầu ra

Các số Nguyên tố an toàn nhỏ hơn 34 là -

5 7 11 23