使用 C++ 打印小于给定数字的所有素数四元组

在这个问题中，我们给定一个正整数 N，我们需要打印所有小于或等于 n 的素数四元组。

素数四元组是由四个素数组成的集合，计算公式为 {p, p+2, p+6, p+8}。示例 - 5 7 11 13。

让我们举个例子来理解这个问题：

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

为了解决这个问题，一个简单的方案是生成所有素数 p 的四元组，并检查 p、p+2、p+6、p+8 是否都是素数。这种方案很容易理解，但对于编译器来说更复杂。

另一种高效的方案是找到所有素数（使用埃拉托斯特尼筛法），并将它们存储在一个数组中，直到某个范围。然后遍历数组，并检查p、p+2、p+6、p+8是否为素数，如果都是素数则打印。

示例

 在线演示

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

输出

所有素数四元组为：

5 7 11 13
11 13 17 19

更新于： 2020年1月17日

121 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告