C++でNまでのすべてのProth素数を出力します

この問題では、整数Nが与えられ、すべてのプロスプライム数を出力する必要があります。 N以下。

プロスプライム数

プロス素数は正の整数であり、その値はn =k ^* として表すことができます。 2 ⁿ + 1.ここで、kは奇数の正の整数、nは正の整数であり、どちらも2 ⁿ を満たします。>k。

例 − 3、5、13…..

トピックをよりよく理解するために例を見てみましょう-

Input: N = 23
Output: 3, 5, 13, 17.

このために、N未満のすべての素数が見つかります（このために、エラトステネスのふるいを使用します） ）。そして、それぞれの素数がプロス数であるかどうかを確認します か否か。そして、すべてのプロス番号を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
int prime[1000];
void SieveOfEratosthenes(int n){
   for (int i = 1; i <= n + 1; i++)
      prime[i] = true;
   prime[1] = false;
   for (int p = 2; p * p <= n; p++) {
      if (prime[p] == true) {
         for (int i = p * p; i <= n; i += p)
            prime[i] = false;
      }
   }
}
bool isTwosExponent(int n){
   return (n && !(n & (n - 1)));
}
bool isaProthNumber(int n){
   int k = 1;
   while (k < (n / k)) {
      if (n % k == 0) {
         if (isTwosExponent(n / k))
            return true;
      }
      k = k + 2;
   }
   return false;
}
bool isaProthPrime(int n){
   if (isaProthNumber(n - 1)) {
      if(prime[n])
         return true;
      else
         return false;
   }
   else
      return false;
}
int main(){
   int n = 23;
   cout<<"Proth Prime Numbers less than or equal to "<<n<<" are :\n";
   SieveOfEratosthenes(n);
   for (int i = 1; i <= n; i++)
      if (isaProthPrime(i))
         cout<<i<<"\t";
   return 0;
}

出力

23以下のプロスプライム数は-

3 5 13 17