Kiểm tra số Primorial Prime trong C++

Khái niệm

Cho số nguyên dương n, kiểm tra xem n có phải là số Primorial Prime hay không. In "YES" nếu có, ngược lại in "NO".

Số Primorial Prime: Là số nguyên tố có dạng pN# + 1 hoặc pN# - 1, trong đó pN# là tích của N số nguyên tố đầu tiên (primorial).

Ví dụ:

• n = 7 → YES. 7 = 2×3 + 1 (N=2, primorial=6).
• n = 29 → YES. 29 = 2×3×5 - 1 (N=3, primorial=30).

Các Primorial Prime đầu tiên: 2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029.

Phương pháp

• Sử dụng sàng Eratosthenes sinh tất cả số nguyên tố đến giới hạn MAX.
• Nếu n không phải số nguyên tố → trả về NO.
• Duyệt qua các số nguyên tố, tính tích lũy (primorial). Kiểm tra nếu product + 1 == n hoặc product - 1 == n → YES.
• Nếu tích vượt quá n mà không thỏa mãn → NO.

Ví dụ (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;
}

Đầu ra

YES