In tất cả Bộ tứ nguyên tố của một số nhỏ hơn nó trong C ++

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

Bộ tứ nguyên tố là tập hợp bốn số nguyên tố được tính là {p, p ⁺² , p ⁺⁶ , p ⁺⁸ }. Ví dụ - 5 7 11 13.

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

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

Để giải quyết vấn đề này, một cách tiếp cận đơn giản là tạo tất cả các phần tư của số chuẩn p và kiểm tra xem tất cả p, p ⁺² , p ⁺⁶ , p ⁺⁸ là các số nguyên tố. Giải pháp này dễ dàng nhưng phức tạp hơn đối với trình biên dịch.

Một cách tiếp cận hiệu quả khác là chọn tất cả các số nguyên tố (sử dụng sàng Eratosthenes) và lưu trữ chúng trong một mảng lên đến một phạm vi nhất định. Và duyệt qua mảng và kiểm tra p, p ⁺² , p ⁺⁶ , p ⁺⁸ là số nguyên tố hay không và in ra nếu tất cả chúng đều là số nguyên tố.

Ví dụ

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

Đầu ra

Tất cả các Bộ tứ nguyên tố đều -

5 7 11 13
11 13 17 19