Đếm số < 10^6 có ước nguyên tố nhỏ nhất là N trong C++

Cho một số nguyên tố num, nhiệm vụ là đếm số lượng số nguyên dương nhỏ hơn 10⁶ có ước nguyên tố nhỏ nhất (minimum prime factor) bằng num.

Ví dụ

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

Input - num = 3 Output - Number of prime factors = 166667

Phương pháp tiếp cận (Sieve Modified)

• Tạo mảng s_prime[] đánh dấu số không phải nguyên tố
• Tạo mảng s_count[] đếm số lượng số có ước nguyên tố nhỏ nhất là i
• Duyệt i từ 2 đến MAX (10⁶): nếu i là nguyên tố (s_prime[i]==0)
• Duyệt bội số j = 2*i, 3*i...: nếu s_prime[j]==0 thì gán s_prime[j]=1 và s_count[i]++
• Kết quả cho num là s_count[num] + 1 (cộng chính num)

Ví dụ code C++

#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++) {
        if (s_prime[i] == 0) {
            for (int j = i * 2; j <= MAX; j += i) {
                if (s_prime[j] == 0) {
                    s_prime[j] = 1;
                    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;
}

Kết quả

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