ধরুন আমাদের একটি সংখ্যা N আছে। আমাদের 1 থেকে N রেঞ্জের মধ্যে প্রায় মৌলিক সংখ্যা খুঁজে বের করতে হবে। একটি সংখ্যাকে প্রায় মৌলিক বলা হয় যখন এর ঠিক দুটি স্বতন্ত্র ফ্যাক্টর থাকে। সংখ্যার যেকোন সংখ্যক নন-প্রাইম ফ্যাক্টর থাকতে পারে, কিন্তু দুটি প্রাইম ফ্যাক্টর হওয়া উচিত। সুতরাং N যদি 2 হয়, তাহলে আউটপুট হবে 2। দুটি সংখ্যা 6 এবং 10 আছে।
এখানে আমরা Eratosthenes পদ্ধতির চালনি ব্যবহার করব। আরও ভাল ধারণা পেতে নিম্নলিখিত বাস্তবায়ন পরীক্ষা করুন৷
উদাহরণ
#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
