C++에서 그보다 작은 수의 모든 프라임 쿼드러플을 인쇄합니다.

이 문제에서 양의 정수 N이 주어지고 n보다 작거나 같은 모든 소수 사중항을 출력해야 합니다.

프라임 쿼드러플렛 {p, p ⁺² 로 계산된 4개의 소수의 집합입니다. ,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;
}

출력

모든 소수 사중항은 -

5 7 11 13
11 13 17 19