C++ में 10^6 से कम उन सभी संख्याओं की गिनती करें जिनका न्यूनतम अभाज्य गुणनखंड N है

हमें एक अभाज्य संख्या दी गई है, मान लीजिए num और कार्य 10^6 से कम उन सभी संख्याओं की संख्या की गणना करना है जिनका न्यूनतम अभाज्य गुणनखंड num के बराबर है।

उदाहरण के लिए

इनपुट - num = 7 आउटपुट - अभाज्य गुणनखंडों की संख्या = 38095 इनपुट - num = 3 आउटपुट - अभाज्य गुणनखंडों की संख्या = 16666

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण

• संख्या इनपुट करें, मान लीजिए num

• लूप शुरू करें, i को 2 से और i को अधिकतम मान से कम या बराबर होना चाहिए और i के मान को बढ़ाएं

• लूप के अंदर, जांचें कि क्या s_prime[i] = 0 है

• लूप बनाएं, j को i * 2 पर सेट करें और j को अधिकतम से कम या बराबर होना चाहिए और j को j + i पर सेट करें

• अब जांचें, यदि s_prime[j] = 1 है

• s_prime[j] = 1 सेट करें

• s_count[i] को 1 से बढ़ाएं

• परिणाम प्रिंट करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000000
// अभाज्य संख्या के लिए एक सिव और
// अभाज्य की संख्या गिनने के लिए
int s_prime[MAX + 4] = {0}, s_count[MAX + 4] = {0};

void create_sieve() {
    // चूंकि 1 अभाज्य संख्या नहीं है
    s_prime[1] = 1;
    // सिव बनाना
    for (int i = 2; i <= MAX; i++) {
        // यदि i एक अभाज्य संख्या है
        if (s_prime[i] == 0) {
            for (int j = i * 2; j <= MAX; j += i) {
                // यदि i न्यूनतम अभाज्य गुणनखंड है
                if (s_prime[j] == 0) {
                    // संख्या j अभाज्य नहीं है
                    s_prime[j] = 1;
                    // उन संख्याओं की गिनती जिनका न्यूनतम अभाज्य गुणनखंड
                    // i है
                    s_count[i]++;
                }
            }
        }
    }
}

int main() {
    // सिव बनाएं
    create_sieve();
    int N = 7;
    cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
    N = 3;
    cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
    return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -

Number of prime factors = 38095 Number of prime factors = 166667