In tất cả bộ tứ nguyên tố (Prime Quadruplet) nhỏ hơn N trong C++

Cho số nguyên dương N, in ra tất cả các bộ tứ nguyên tố (prime quadruplet) nhỏ hơn hoặc bằng N.

Bộ tứ nguyên tố là tập 4 số nguyên tố dạng {p, p+2, p+6, p+8}. Ví dụ: 5, 7, 11, 13.

Ví dụ:

Input: N = 15 Output: 5 7 11 13

Cách giải: Sinh tất cả số nguyên tố bằng sàng Eratosthenes, lưu vào mảng. Duyệt mảng kiểm tra p, p+2, p+6, p+8 có phải nguyên tố không.

Chương trình minh họa

#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 << "Tất cả bộ tứ nguyên tố:\n";
    printPrimeQuadruplet(20);
    return 0;
}

Kết quả

Tất cả bộ tứ nguyên tố là:

5 7 11 13
11 13 17 19