จำนวนเฉพาะตัวประกอบที่ไม่ซ้ำกันสูงสุดในช่วง 1 ถึง N ใน C++

ภาพรวมปัญหา

หาจำนวนเฉพาะตัวประกอบที่ไม่ซ้ำกันสูงสุดที่ตัวเลขในช่วง [1, N] สามารถมีได้

ตัวอย่าง

Input: N = 100
Output: 3
Explanation: 30 = 2 × 3 × 5 มีตัวประกอบเฉพาะ 3 ตัว

Input: N = 300
Output: 4

แนวทางแก้ปัญหา

• ใช้ Sieve of Eratosthenes หาจำนวนเฉพาะทั้งหมด ≤ N
• คูณจำนวนเฉพาะตามลำดับ (2, 3, 5, 7, ...) จนกว่าผลคูณจะเกิน N
• จำนวนเฉพาะที่คูณได้ = คำตอบ

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

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

int MaxPrime(int N) {
    if (N < 2) return 0;
    
    bool Arr[N+1];
    memset(Arr, true, sizeof(Arr));
    int pro = 1, max = 0;
    
    for (int p = 2; p*p <= N; p++) {
        if (Arr[p] == true) {
            for (int i = p*2; i <= N; i += p)
                Arr[i] = false;
            
            pro *= p;
            if (pro > N) return max;
            max++;
        }
    }
    return max;
}

int main() {
    int N = 300;
    cout << MaxPrime(N);
    return 0;
}

ผลลัพธ์

4