หาจำนวนการดำเนินการสูงสุดลด N ให้เหลือ 1 ใน Python

โจทย์: N = P! / Q! ลด N เป็น 1 โดยแทนที่ N ← N/X เมื่อ X หาร N ลงตัว หาจำนวนขั้นตอนสูงสุด (คือ จำนวนเฉพาะในการแยกตัวประกอบของ N)

ตัวอย่าง: P=7, Q=4 → N = 7!/4! = 5×6×7 = 210 = 2×3×5×7 → 4 ขั้นตอน

อัลกอริทึม: Sieve + Prefix Sum

1. Sieve คำนวณจำนวนเฉพาะในการแยกตัวประกอบของทุกตัวเลข ≤ N (factors[i])
2. factors[j] = factors[j/i] + 1 สำหรับทุกจำนวนเฉพาะ i
3. Prefix sum: factors[i] += factors[i-1] → factors[i] = จำนวนเฉพาะใน i! (รวมความหลาย)
4. คำตอบ = factors[P] - factors[Q]

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

N = 1000005
factors = [0] * N

def get_prime_facts():
    for i in range(2, N):
        if factors[i] == 0:  # i is prime
            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, b = 7, 4
print(factors[a] - factors[b])  # 4

ผลลัพธ์

4

สรุป: ใช้ Sieve แบบปรับเปลี่ยน คำนวณ Ω(n) (จำนวนเฉพาะรวมความหลาย) สำหรับทุก n ≤ 10⁶ แล้ว prefix sum ได้ Ω(n!) คำตอบ = Ω(P!) - Ω(Q!) = Ω(P!/Q!)