1 से N तक ऑलमोस्ट अभाज्य संख्याओं की गिनती खोजें C++ में

मान लीजिए हमारे पास एक संख्या N है। हमें 1 से N की रेंज में ऑलमोस्ट अभाज्य संख्याएं खोजनी हैं। एक संख्या को ऑलमोस्ट अभाज्य कहा जाता है जब उसके ठीक दो अलग-अलग अभाज्य गुणनखंड हों। संख्याओं में कितने भी गैर-अभाज्य गुणनखंड हो सकते हैं, लेकिन दो अभाज्य गुणनखंड होने चाहिए। तो यदि N 21 है, तो आउटपुट 8 होगा।

यहां हम एराटोस्थनीज की छलनी दृष्टिकोण का उपयोग करेंगे। बेहतर विचार पाने के लिए निम्नलिखित कार्यान्वयन की जांच करें।

उदाहरण

#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