พิมพ์ Prime Quadruplet ทั้งหมดของตัวเลขน้อยกว่ามันใน C++

ในปัญหานี้ เราจะได้รับจำนวนเต็มบวก N และต้องพิมพ์ Prime Quadruplet ทั้งหมดที่น้อยกว่าหรือเท่ากับ N

Prime Quadruplet คือ เซตของจำนวนเฉพาะ 4 ตัวที่คำนวณได้จาก {p, p+2, p+6, p+8} ตัวอย่าง - 5 7 11 13

ตัวอย่างเพื่อความเข้าใจ

Input: N = 15
Output: 5 7 11 13

เพื่อแก้ปัญหานี้ วิธีง่ายคือสร้าง quadruplet ของจำนวนเฉพาะ p ทั้งหมดและตรวจสอบว่า p, p+2, p+6, p+8 เป็นจำนวนเฉพาะทั้งหมดหรือไม่ วิธีนี้ง่ายแต่ซับซ้อนสำหรับคอมไพเลอร์

วิธีที่มีประสิทธิภาพมากกว่าคือหาจำนวนเฉพาะทั้งหมด (โดยใช้ Sieve of Eratosthenes) และเก็บไว้ใน array จนถึงช่วงที่กำหนด จากนั้นวนลูปตรวจสอบ 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;
}

ผลลัพธ์

All prime Quadruplets are -

5 7 11 13
11 13 17 19