Tìm số phép toán tối đa giảm N về 1 trong Python

Cho hai số P, Q tạo thành N = P! / Q!. Giảm N về 1 bằng tối đa số phép toán. Mỗi phép: N = N / X nếu N chia hết cho X. Trả về số phép tối đa.

Ví dụ: P = 7, Q = 4 → N = 210 = 2×3×5×7 → 4 phép (chia cho 2,3,5,7).

Thuật toán Sieve đếm ước nguyên tố

1. Tính trước mảng factors[i] = số ước nguyên tố của i (có multiplicity).
2. Dùng sieve: với mỗi số nguyên tố i, duyệt bội số j, factors[j] = factors[j//i] + 1.
3. Tính prefix sum: factors[i] += factors[i-1] → factors[i] = tổng số ước nguyên tố của i!.
4. Kết quả = factors[P] - factors[Q].

Ví dụ code

N = 1000005
factors = [0] * N

def get_prime_facts():
    for i in range(2, N):
        if factors[i] == 0:
            for j in range(i, N, i):
                factors[j] = factors[j // i] + 1
    for i in range(1, N):
        factors[i] += factors[i - 1]

get_prime_facts()
a = 7
b = 4
print(factors[a] - factors[b])

Input

7, 4

Output

4