C++-এ 10^6-এর চেয়ে ছোট যেসব সংখ্যার ন্যূনতম প্রাইম ফ্যাক্টর N তাদের গণনা

আমাদের একটি প্রাইম সংখ্যা দেওয়া আছে, যেমন num, এবং আমাদের কাজ হল 10^6-এর চেয়ে ছোট যেসব সংখ্যার ন্যূনতম প্রাইম ফ্যাক্টর num-এর সমান তাদের গণনা করা।

উদাহরণ

ইনপুট − num = 7 আউটপুট − প্রাইম ফ্যাক্টরের সংখ্যা = 38095

ইনপুট − num = 3 আউটপুট − প্রাইম ফ্যাক্টরের সংখ্যা = 16666

প্রোগ্রামে ব্যবহৃত পদ্ধতি

সংখ্যা ইনপুট নিন, যেমন num
i = 2 থেকে i <= max value পর্যন্ত লুপ শুরু করুন
লুপের ভিতরে চেক করুন s_prime[i] == 0
লুপ তৈরি করুন, j = i * 2 থেকে j <= max এবং 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() {
    // ১ প্রাইম নয়
    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