Pierpont Prime trong C ++

Trong bài toán này, chúng ta được cho một số n. Nhiệm vụ của chúng tôi là in tất cả Các số nguyên tố có đính kèm ít hơn n.

Pierpont Prime number là một loại số nguyên tố đặc biệt có dạng,

p =2 ⁱ . 3 ^k + 1.

Trong đó p là số nguyên tố và i và k là một số số nguyên.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - n =50

Đầu ra - 2, 3, 5, 7, 13, 17, 19, 37

Để giải quyết vấn đề này, chúng ta phải tìm tất cả các số nguyên tố tuân theo điều kiện. Đối với điều này, chúng ta sẽ tìm một số có các thừa số là 2 và 3. Và tìm tất cả các số nguyên tố. Và in những số đó là cả hai, một số nguyên tố tuân theo điều kiện.

Ví dụ

Chương trình thể hiện việc triển khai giải pháp của chúng tôi,

#include <bits/stdc++.h>
using namespace std;
void printPierpontPrimes(int n){
   bool arr[n+1];
   memset(arr, false, sizeof arr);
   int two = 1, three = 1;
   while (two + 1 < n) {
      arr[two] = true;
      while (two * three + 1 < n) {
         arr[three] = true;
         arr[two * three] = true;
         three *= 3;
      }
      three = 1;
      two *= 2;
   }
   vector<int> primes;
   for (int i = 0; i < n; i++)
   if (arr[i])
      primes.push_back(i + 1);
   memset(arr, false, sizeof arr);
   for (int p = 2; p * p < n; p++) {
      if (arr[p] == false)
         for (int i = p * 2; i< n; i += p)
            arr[i] = true;
   }
   for (int i = 0; i < primes.size(); i++)
      if (!arr[primes[i]])
      cout<<primes[i]<<"\t";
}
int main(){
   int n = 50;
   cout<<"All Pierpont Prime Numbers less than "<<n<<" are :\n";
   printPierpontPrimes(n);
   return 0;
}

Đầu ra

All Pierpont Prime Numbers less than 50 are :
2    3    5    7    13    17    19    37