Số nguyên tố Pierpont trong C++

Trong bài toán này, chúng ta được cho một số n. Nhiệm vụ là in tất cả các số nguyên tố Pierpont nhỏ hơn n.

Số nguyên tố Pierpont là một loại số nguyên tố đặc biệt có dạng:

p = 2ⁱ . 3^k + 1.

Trong đó p là số nguyên tố, i và k là các số nguyên.

Ví dụ minh họa:

Đầu vào - n = 50

Kết quả - 2, 3, 5, 7, 13, 17, 19, 37

Để giải bài toán, ta phải tìm tất cả các số nguyên tố thỏa mãn điều kiện. Ta sẽ tìm các số có thừa số là lũy thừa của 2 và 3. Sau đó tìm tất cả các số nguyên tố. Và in ra những số vừa là số nguyên tố vừa thỏa mãn điều kiện.

Chương trình minh họa

#include <bits/stdc++.h> 
using namespace std; 

void printPierpontPrimes(int n) { 
    bool arr[n+1]; 
    memset(arr, false, sizeof arr); 
    int two = 1, three = 1; 
    while (two + 1 < n) { 
        arr[two] = true; 
        while (two * three + 1 < n) { 
            arr[three] = true; 
            arr[two * three] = true; 
            three *= 3; 
        } 
        three = 1; 
        two *= 2; 
    } 
    vector<int> primes; 
    for (int i = 0; i < n; i++) 
        if (arr[i]) 
            primes.push_back(i + 1); 
    memset(arr, false, sizeof arr); 
    for (int p = 2; p * p < n; p++) { 
        if (arr[p] == false) 
            for (int i = p * 2; i < n; i += p) 
                arr[i] = true; 
    } 
    for (int i = 0; i < primes.size(); i++) 
        if (!arr[primes[i]]) 
            cout << primes[i] << "\t"; 
} 

int main() { 
    int n = 50; 
    cout << "Tất cả các số nguyên tố Pierpont nhỏ hơn " << n << " là:\n"; 
    printPierpontPrimes(n); 
    return 0; 
}

Kết quả

Tất cả các số nguyên tố Pierpont nhỏ hơn 50 là: 2   3   5   7   13   17   19   37