C++-এ প্রাইম্যালিটি টেস্ট (Primality Test - Check if Number is Prime)

এই সমস্যাতে, একটি সংখ্যা N দেওয়া থাকে। সেটি প্রাইম (মৌলিক) সংখ্যা কিনা তা চেক করতে হবে।

প্রাইম সংখ্যা

যে সংখ্যাটি শুধু ১ এবং নিজে দিয়ে ভাগ যায়। উদাহরণ: 2, 3, 5, 7, 11...

পদ্ধতি ১: অপ্টিমাইজড ট্রায়াল ডিভিশন (O(√n))

• n ≤ 1 হলে প্রাইম নয়
• n ≤ 3 হলে প্রাইম
• 2 বা 3 দিয়ে ভাগ হলে প্রাইম নয়
• 5 থেকে √n পর্যন্ত 6-স্টেপে লুপ (i এবং i+2 চেক করুন)

C++ প্রোগ্রাম উদাহরণ (ট্রায়াল ডিভিশন)

#include <iostream>
using namespace std;

bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

int main() {
    int n = 341;
    if (isPrimeNumber(n))
        cout << n << " is prime Number.";
    else
        cout << n << " is not prime Number.";
    return 0;
}

আউটপুট

341 is not prime Number.

পদ্ধতি ২: ফার্মেটস লিটেল থিওরেম (Probabilistic - O(k log³n))

প্রাইম N-এর জন্য: a^(N-1) ≡ 1 (mod N) সব a ∈ [1, N-1] এর জন্য।

k বার র‍্যান্ডম a নিয়ে টেস্ট করুন। k বড় হলে নির্ভুলতা বেড়ে।

C++ প্রোগ্রাম উদাহরণ (ফার্মেটস)

#include <iostream>
#include <math.h>
#include <cstdlib>
using namespace std;

int power(int a, unsigned int n, int p) {
    int res = 1;
    a = a % p;
    while (n > 0) {
        if (n & 1) res = (res * a) % p;
        n >>= 1;
        a = (a * a) % p;
    }
    return res;
}

int gcd(int a, int b) {
    if (a < b) return gcd(b, a);
    if (a % b == 0) return b;
    return gcd(b, a % b);
}

bool isPrime(unsigned int n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    
    while (k--) {
        int a = 2 + rand() % (n - 4);
        if (gcd(n, a) != 1) return false;
        if (power(a, n - 1, n) != 1) return false;
    }
    return true;
}

int main() {
    int k = 3, n = 23;
    if (isPrime(n, k))
        cout << n << " is a prime number";
    else
        cout << n << " is not a prime number";
    return 0;
}

আউটপুট

23 is a prime number