In tất cả các số nguyên tố Proth lên đến N trong C ++

Trong bài toán này, chúng ta được cho một số nguyên N và chúng ta phải in tất cả số nguyên tố nhỏ hơn hoặc bằng N.

Số nguyên tố theo thứ bậc

Số nguyên tố theo thứ tự là một số nguyên dương có giá trị có thể được biểu diễn bằng n =k ^* 2 ⁿ + 1. trong đó k là số nguyên dương lẻ và n là số nguyên dương và cả hai đều thỏa mãn 2 ⁿ > k.

Ví dụ - 3, 5, 13… ..

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

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

Đối với điều này, chúng tôi 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 tôi sẽ sử dụng sàng của Eratosthenes ). Và kiểm tra xem mỗi số nguyên tố có phải là số thứ tự không hay không. Và in tất cả các số proth.

Ví dụ

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

Đầu ra

Số nguyên tố Proth nhỏ hơn hoặc bằng 23 là -

3 5 13 17