আমাদের একটি মৌলিক সংখ্যা দেওয়া হয়েছে ধরা যাক, সংখ্যা এবং কাজটি হল 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