在C ++中打印所有小于其数量的Prime Quadruplet

Z时代
2024-01-10
分类：综合

在这个问题中，我们得到一个正整数N，并且我们必须打印所有小于或等于n的素数四元组。

素数四元组是计算为{p，p ⁺²，p ⁺⁶，p ⁺⁸ }的四个素数的集合。示例-5 7 11 13。

让我们以一个例子来了解问题-

Input: N = 15
Output: 5 7 11 13.

为了解决这个问题，一种简单的方法是生成所有质数为p的四元组，并检查所有p，p ⁺²，p ⁺⁶，p ⁺⁸是否均为质数。此解决方案很简单，但对于编译器而言则更为复杂。

另一种有效的方法是创建所有质数（使用Eratosthenes的筛子）并将它们存储在一定范围内的数组中。然后遍历数组并检查p，p ⁺²，p ⁺⁶，p ⁺⁸是否为素数，并打印它们是否均为素数。

示例

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
bool prime[MAX];
void primeNumberGenerator() {
   memset(prime, true, sizeof(prime));
   for (int p = 2; p * p < MAX; p++) {
      if (prime[p] == true) {
         for (int i = p * 2; i < MAX; i += p)
            prime[i] = false;
      }
   }
}
void printPrimeQuadruplet(int n) {
   for (int i = 0; i < n - 7; i++) {
      if (prime[i] && prime[i + 2] && prime[i + 6] && prime[i + 8]) {
         cout<<i<<" "<<i+2<<" "<<i+6<<" "<<i+8<<endl;
      }
   }
}
int main() {
   primeNumberGenerator();
   int n = 42;
   cout<<"All prime Quadruplets are :\n";
   printPrimeQuadruplet(20);
   return 0;
}