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

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

उदाहरण के लिए

Input − num = 7
Output − Number of prime factors = 38095

Input − num = 3
Output − Number of prime factors = 16666

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

• संख्या दर्ज करें मान लें कि संख्या है

• लूप को 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
// a sieve for prime number and
// to count the number of prime
int s_prime[MAX + 4] = { 0 }, s_count[MAX + 4] = { 0 };
void create_sieve(){
   // As 1 is not a prime number
   s_prime[1] = 1;
   // creating the sieve
   for (int i = 2; i <= MAX; i++){
      // if i is a prime number
      if (s_prime[i] == 0){
         for (int j = i * 2; j <= MAX; j += i){
            // if i is the least prime factor
            if (s_prime[j] == 0){
               // The number j is not a prime
               s_prime[j] = 1;
               // counting the numbers whose least prime factor
               // is i
               s_count[i]++;
            }
         }
      }
   }
}
int main(){
   // create the sieve
   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