C++-এ N পর্যন্ত অল্টারনেট প্রাইম সংখ্যা (Alternate Primes till N)

এখানে আমরা দেখব N পর্যন্ত সব অল্টারনেট প্রাইম সংখ্যা প্রিন্ট করার উপায়। অল্টারনেট প্রাইম সংখ্যাগুলো নিচের মতো। ধরি N = 15। তাহলে N পর্যন্ত প্রাইম সংখ্যাগুলো হলো {2, 3, 5, 7, 11, 13}। অল্টারনেট প্রাইম সংখ্যাগুলো হলো {2, 5, 11}। দেখি কীভাবে এই সমস্যা সমাধান করা যায়।

অ্যালগরিদম

printAlternatePrime(N)

Begin
    N+1 সাইজের একটি বুলিয়ান অ্যারে prime ডিফাইন করুন, এবং ১ দিয়ে ফিল করুন।
    for p := 2, p² less than N, p বাড়াতে ১, do
        if prime[p] is true, then
            p-এর সব গুণককে prime অ্যারেতে ০ করুন
        end if
    done
    ফ্ল্যাগ সেট করুন
    for p := 2 to n, do
        if prime[p] is true, then
            if flag is set, then
                print p, and reset the flag
            else
                set the flag
            end if
        end if
    done
End

উদাহরণ

#include<iostream>
using namespace std;
void printAlternatePrime(int n) {
    bool prime[n + 1];
    for(int i = 0; i <= n; i++) {
        prime[i] = true;
    }
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) // সব গুণক হবে false
                prime[i] = false;
        }
    }
    bool prime_flag = true;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            if (prime_flag) {
                cout << p << " ";
                prime_flag = false;
            } else {
                prime_flag = true; // নেক্সট প্রাইম প্রিন্ট করার জন্য সেট
            }
        }
    }
}
main() {
    int n;
    cout << "Enter upper limit: ";
    cin >> n;
    cout << "Alternate prime numbers are: ";
    printAlternatePrime(n);
}

আউটপুট

Enter upper limit: 20 Alternate prime numbers are: 2 5 11 17