ตรวจสอบว่าเลขจำนวนเต็มสามารถเขียนเป็นผลรวมของสองเซมีไพรม์ได้หรือไม่ใน Python

ภาพรวม

บทความนี้แสดงวิธีตรวจสอบว่าเลข n สามารถเขียนในรูปผลรวมของเซมีไพรม์ (semi-prime) สองจำนวนได้หรือไม่ เซมีไพรม์คือเลขที่เป็นผลคูณของจำนวนเฉพาะสองจำนวน (อาจเป็นจำนวนเฉพาะตัวเดียวกันได้ เช่น 4 = 2×2)

เซมีไพรม์ตัวอย่าง (1-100)

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95

อัลกอริทึม

1. สร้างรายการเซมีไพรม์ทั้งหมดจนถึงค่าสูงสุดที่กำหนด (MAX = 10000)
2. ใช้การแยกตัวประกอบเฉพาะเพื่อตรวจสอบว่าเลขแต่ละจำนวนเป็นเซมีไพรม์หรือไม่
3. ตรวจสอบว่ามีคู่เซมีไพรม์ (a, b) ที่ a + b = n โดยวนลูป a จนถึง n//2 และตรวจสอบว่า n-a เป็นเซมีไพรม์หรือไม่

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

MAX = 10000
nums = []
s_prime_flags = [False] * MAX

def get_semi_primes():
    for i in range(2, MAX):
        count = 0
        num = i
        j = 2
        while count < 2 and j * j <= num:
            while num % j == 0:
                num //= j
                count += 1
            j += 1
        if num > 1:
            count += 1
        if count == 2:
            s_prime_flags[i] = True
            nums.append(i)

def solve(n):
    get_semi_primes()
    i = 0
    while nums[i] <= n // 2:
        if s_prime_flags[n - nums[i]]:
            return True
        i += 1
    return False

n = 108
print(solve(n))  # True (14 + 94)

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

โค้ดใช้การคัดกรองเซมีไพรม์ล่วงหน้า (precompute) เพื่อให้การตรวจสอบแต่ละค่า n รวดเร็วขึ้น เหมาะสำหรับการประมวลผลหลายคำถาม (multiple queries)