C++-এ পায়ারপয়েন্ট প্রাইম (Pierpont Prime)

এই সমস্যাতে, একটি সংখ্যা n দেওয়া আছে। আমাদের কাজ হলো n-র চেয়ে ছোট সব পায়ারপয়েন্ট প্রাইম সংখ্যা প্রিন্ট করা।

পায়ারপয়েন্ট প্রাইম হলো একটি বিশেষ ধরনের প্রাইম সংখ্যা যার রূপ:

p = 2ⁱ × 3^k + 1

যেখানে p হলো একটি প্রাইম সংখ্যা, এবং i ও k যেকোনো পূর্ণসংখ্যা।

উদাহরণ:

ইনপুট - n = 50

আউটপুট - 2, 3, 5, 7, 13, 17, 19, 37

সমাধানের জন্য, আমরা শর্ত অনুযায়ী সব প্রাইম সংখ্যা বের করব। ২ এবং ৩-এর ঘাতের গুণফল যোগ ১ হলে প্রাইম হয় এমন সংখ্যাগুলো খুঁজে বের করব।

উদাহরণ

সমাধানের প্রোগ্রাম:

#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 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 << "All Pierpont Prime Numbers less than " << n << " are :\n";
    printPierpontPrimes(n);
    return 0;
}

আউটপুট

All Pierpont Prime Numbers less than 50 are : 2   3   5   7   13   17   19   37