Kiểm tra tổng các phần tử nguyên tố trong mảng có phải số nguyên tố không trong Python

Cho mảng nums. Kiểm tra xem tổng của tất cả các phần tử nguyên tố trong mảng có phải số nguyên tố hay không.

Ví dụ: nums=[1,2,4,5,3,3] → tổng nguyên tố = 2+5+3+3=13 → 13 là nguyên tố → True.

Thuật toán

• Dùng sàng Eratosthenes (MAX=10000) để tính trước mảng sieve đánh dấu số nguyên tố.
• Duyệt mảng, cộng dồn các phần tử là số nguyên tố (theo sieve).
• Kiểm tra tổng có phải nguyên tố (theo sieve).

Ví dụ code

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):  # sửa 2**i thành 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))

Đầu vào

[1,2,4,5,3,3]

Đầu ra

True