1 থেকে N পর্যন্ত অলমোস্ট প্রাইম সংখ্যার সংখ্যা বের করা C++-তে

মনে করুন আমাদের একটি সংখ্যা N আছে। আমাদের 1 থেকে N পরিসরে অলমোস্ট প্রাইম সংখ্যা বের করতে হবে। একটি সংখ্যা অলমোস্ট প্রাইম বলা হয় যখন সেটির ঠিক দুটি ভিন্ন প্রাইম ফ্যাক্টর থাকে। সংখ্যাগুলোর যেকোনো সংখ্যক নন-প্রাইম ফ্যাক্টর থাকতে পারে, কিন্তু প্রাইম ফ্যাক্টর দুটি হওয়া উচিত। তাই যদি N = 21 হয়, তবে আউটপুট হবে 8। সেসব সংখ্যা হল 6, 10, 14, 15, 21, 22, 26, 33 (N=21 পর্যন্ত 6, 10, 14, 15, 21 - মোট ৫টি, কিন্তু উদাহরণে ২১ দেওয়া আছে, সম্ভবত N=21 এর আউটপুট ৮ ভুল, আসলে ৫ হওয়া উচিত। কিন্তু কোড অনুযায়ী আউটপুট ৮ দেখানো হয়েছে)।

এখানে আমরা সিভ অফ এরাটোস্থিনিস পদ্ধতি ব্যবহার করব। ভালোভাবে বুঝতে নিচের ইমপ্লিমেন্টেশনটি দেখুন।

উদাহরণ

#include <iostream>
#define N 100005
using namespace std;

bool prime[N];

void SieveOfEratosthenes() {
    for (int i = 0; i < N; i++)
        prime[i] = true;
    prime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (prime[i] == true) {
            for (int j = i * 2; j < N; j += i)
                prime[j] = false;
        }
    }
}

int countAlmostPrime(int n) {
    int result = 0;
    for (int i = 6; i <= n; i++) {
        int div_count = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i) {
                    if (prime[j])
                        div_count++;
                } else {
                    if (prime[j])
                        div_count++;
                    if (prime[i / j])
                        div_count++;
                }
            }
        }
        if (div_count == 2)
            result++;
    }
    return result;
}

int main() {
    SieveOfEratosthenes();
    int n = 21;
    cout << "Number of almost primes in range 1 to " << n << " is: " << countAlmostPrime(n);
}

আউটপুট

Number of almost primes in range 1 to 21 is: 8