ตรวจสอบว่าเป็นจำนวนเฉพาะพรีโมเรียล (Primorial Prime) หรือไม่ใน C++

แนวคิด

จำนวนเฉพาะพรีโมเรียล (Primorial Prime) คือจำนวนเฉพาะที่อยู่ในรูปแบบ pN# + 1 หรือ pN# - 1 โดยที่ pN# คือผลคูณของจำนวนเฉพาะ N ตัวแรก (เรียกว่า Primorial)

ตัวอย่าง: - 7 = 2×3 + 1 = 6 + 1 → YES (N=2) - 29 = 2×3×5 - 1 = 30 - 1 → YES (N=3) - จำนวนเฉพาะพรีโมเรียลแรกๆ: 2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029

วิธีการแก้ปัญหา

1. สร้างจำนวนเฉพาะทั้งหมดในช่วงด้วย Sieve of Eratosthenes
2. ตรวจสอบว่า N เป็นจำนวนเฉพาะหรือไม่ ถ้าไม่ใช่ พิมพ์ NO
3. เริ่มจากจำนวนเฉพาะตัวแรก (2) คูณจำนวนเฉพาะถัดไปทีละตัว และตรวจสอบว่า product + 1 = N หรือ product - 1 = N หรือไม่
4. หากเงื่อนไขใดเป็นจริง N คือ Primorial Prime มิฉะนั้นไม่ใช่

ตัวอย่างโค้ด C++

// CPP program to check Primorial Prime
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
vector<int> arr1;
bool prime1[MAX];

void SieveOfEratosthenes1(){
    memset(prime1, true, sizeof(prime1));
    for (int p = 2; p * p < MAX; p++) {
        if (prime1[p] == true) {
            for (int i = p * 2; i < MAX; i += p)
                prime1[i] = false;
        }
    }
    for (int p = 2; p < MAX; p++)
        if (prime1[p])
            arr1.push_back(p);
}

bool isPrimorialPrime1(long n){
    if (!prime1[n]) return false;
    long long product1 = 1;
    int i = 0;
    while (product1 < n) {
        product1 = product1 * arr1[i];
        if (product1 + 1 == n || product1 - 1 == n)
            return true;
        i++;
    }
    return false;
}

int main(){
    SieveOfEratosthenes1();
    long n = 29;
    if (isPrimorialPrime1(n))
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

ผลลัพธ์

YES