हमें एक अभाज्य संख्या दी गई है मान लीजिए, संख्या और कार्य 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
