C++에서 N까지 모든 Proth 소수를 인쇄합니다.

이 문제에서 정수 N이 주어지고 모든 prothprime 숫자를 출력해야 합니다. N보다 작거나 같음.

프로스 프라임 번호

proth 소수는 값이 n =k ^* 로 표시될 수 있는 양의 정수입니다. 2 ⁿ + 1. 여기서 k는 홀수 양의 정수이고 n은 양의 정수이며 둘 다 2 ⁿ 을 충족합니다.> ㅁ.

예 − 3, 5, 13…..

주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

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

이를 위해 우리는 N보다 작은 모든 소수를 찾을 것입니다(이를 위해 우리는 에라토스테네스의 체를 사용할 것입니다. ). 그리고 각 소수가 proth number인지 확인합니다. 아니면. 그리고 모든 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