นับจำนวนน้อยกว่า 10⁶ ที่มีตัวประกอบเฉพาะน้อยที่สุดเป็น N ใน C++

เราได้รับจำนวนเฉพาะ num งานคือการนับจำนวนเต็มน้อยกว่า 10⁶ ที่มีตัวประกอบเฉพาะน้อยที่สุด (least prime factor) เท่ากับ num

ตัวอย่าง

Input − num = 7 Output − 38095

Input − num = 3 Output − 166667

แนวทางการแก้ปัญหา (Modified Sieve)

• สร้าง sieve ปกติ แต่เพิ่มการนับ: s_count[i] = จำนวนที่มี LPF = i
• ในลูป sieve: ถ้า i เป็นเฉพาะ (s_prime[i]==0) ให้วน j = 2i, 3i... ถ้า s_prime[j]==0 (ยังไม่มี LPF) ตั้ง s_prime[j]=1 และเพิ่ม s_count[i]++
• คำตอบคือ s_count[N] + 1 (บวก 1 สำหรับตัว N เอง)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000000
int s_prime[MAX + 4] = {0};
int s_count[MAX + 4] = {0};

void createSieve() {
    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() {
    createSieve();
    int N = 7;
    cout << "Number of integers with LPF = " << N << ": " << s_count[N] + 1 << endl;
    N = 3;
    cout << "Number of integers with LPF = " << N << ": " << s_count[N] + 1 << endl;
    return 0;
}

ผลลัพธ์

Number of integers with LPF = 7: 38095
Number of integers with LPF = 3: 166667