C++-এ দেওয়া প্রোডাক্টের জন্য দুটি ডISTINCT প্রাইম নম্বর খুঁজে বের করা

সমস্যা

একটি ইন্টিজার N দেওয়া। দুটি ভিন্ন প্রাইম নম্বর p, q খুঁজুন যাতে p * q = N।

অ্যালগরিদম: সিভ অফ এরাটোস্থেনিস + চেক

N পর্যন্ত প্রাইম নম্বরগুলো সিভ দিয়ে জেনারেট করুন।
প্রতিটি প্রাইম p (২ থেকে sqrt(N)) এর জন্য:
- যদি N % p == 0 হয়, তবে q = N/p।
- যদি q প্রাইম হয় এবং q != p, তবে পাওয়া গেলো।
না পেলে "No prime pair exist"।

C++ কোড

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

void sieve(int n, vector<bool>& isPrime) {
    isPrime.assign(n+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p=2; p*p<=n; p++)
        if (isPrime[p])
            for (int i=p*p; i<=n; i+=p) isPrime[i] = false;
}

void calcPairPrime(int n) {
    vector<bool> isPrime;
    sieve(n, isPrime);
    for (int p=2; p*p<=n; p++) {
        if (isPrime[p] && n%p == 0) {
            int q = n/p;
            if (q != p && isPrime[q]) {
                cout << p << " " << q;
                return;
            }
        }
    }
    cout << "No prime pair exist";
}

int main() { calcPairPrime(24); }

আউটপুট

No prime pair exist

(২৪ = ২×১২, ৩×৮, ৪×৬ — কোনো পেয়ারই দুটি প্রাইম নয়।)