Số lượng ước nguyên tố khác nhau tối đa trong khoảng [1, N] C++

Cho số nguyên N. Tìm số lượng ước nguyên tố khác nhau tối đa mà một số nào đó trong khoảng [1, N] có thể có.

Ví dụ

Input: N = 100 → Output: 3
Giải thích: Số 30 = 2 * 3 * 5 có 3 ước nguyên tố khác nhau. Không số nào ≤ 100 có 4 ước nguyên tố khác nhau.

Input: N = 300 → Output: 4
Giải thích: 2 * 3 * 5 * 7 = 210 ≤ 300. 2*3*5*7*11 = 2310 > 300.

Thuật toán

Số có nhiều ước nguyên tố khác nhau nhất là tích của các số nguyên tố nhỏ nhất liên tiếp: 2 * 3 * 5 * 7 * 11 * ...

Duyệt các số nguyên tố theo thứ tự, nhân tích lũy cho đến khi tích > N. Số lượng số nguyên tố đã nhân được là đáp án.

Chương trình C++ (Sieve của Eratosthenes)

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

int maxUniquePrimeFactors(int N) {
    if (N < 2) return 0;
    
    // Sieve tìm số nguyên tố
    vector isPrime(N + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= N; p++)
        if (isPrime[p])
            for (int i = p * p; i <= N; i += p)
                isPrime[i] = false;
    
    long long product = 1;
    int count = 0;
    for (int p = 2; p <= N; p++) {
        if (isPrime[p]) {
            if (product * p > N) break;
            product *= p;
            count++;
        }
    }
    return count;
}

int main() {
    int N = 300;
    cout << maxUniquePrimeFactors(N); // Output: 4
    return 0;
}

Kết quả

4

Phân tích độ phức tạp

• Sieve: O(N log log N)
• Duyệt số nguyên tố: O(N / log N)
• Nhìn chung rất nhanh cho N ≤ 10⁷.