在C ++中将所有Proth素数打印为N

在这个问题中，我们得到一个整数N，我们必须打印所有小于或等于N的proth质数。

普罗斯素数

Proth质数是一个正整数，其值可以表示为n = k ^* 2 ⁿ +1。其中k是一个奇数正整数，n是一个正整数，并且都满足2 ⁿ > k。

示例-3、5、13…..

让我们举个例子来更好地理解这个话题-

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

为此，我们将找到所有小于N的质数（为此，我们将使用Eratosthenes筛子）。并检查每个素数是否为真数。并打印所有proth数字。

示例

#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的Proth素数为-

3 5 13 17