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

โจทย์: กำหนด Array nums ตรวจสอบว่าผลรวมของสมาชิกที่เป็น Prime ใน Array นั้น เองก็เป็น Prime อีกด้วยหรือไม่

ตัวอย่าง

nums = [1,2,4,5,3,3] → True (Primes: 2,5,3,3 → Sum=13 ซึ่งเป็น Prime)

อัลกอริทึม (Sieve of Eratosthenes)

1. สร้าง Sieve ขนาด MAX (10000) หา Prime ทั้งหมด
2. วน Array รวมค่าที่เป็น Prime
3. ตรวจสอบว่าผลรวมเป็น Prime ด้วย Sieve เดียวกัน

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

MAX = 10000
sieve = [True] * MAX

def generate_list_of_primes():
    sieve[0] = False
    sieve[1] = False
    for i in range(2, MAX):
        if sieve[i]:
            for j in range(2*i, MAX, i):  # Fixed: 2*i not 2**i
                sieve[j] = False

def solve(arr):
    generate_list_of_primes()
    total = 0
    for i in range(len(arr)):
        if sieve[arr[i]]:
            total += arr[i]
    if sieve[total]:
        return True
    return False

nums = [1,2,4,5,3,3]
print(solve(nums))

Input / Output

Input: [1,2,4,5,3,3]
Output: True

หมายเหตุ: โค้ดต้นฉบับมี Bug ที่ range(2**i, MAX, i) ควรเป็น range(2*i, MAX, i) (เริ่มจาก 2*i ไม่ใช่ 2 ยกกำลัง i) โค้ดข้างบนแก้ไขแล้ว