Kiểm tra xem số nguyên có thể biểu diễn dưới dạng tổng của hai bán số nguyên tố trong Python

Giả sử chúng ta có một số n, cần kiểm tra xem n có thể biểu diễn dưới dạng tổng của hai bán số nguyên tố (semi-prime) hay không.

Bán số nguyên tố là số có thể biểu diễn dưới dạng tích của hai số nguyên tố. Các bán số nguyên tố đầu tiên (trong khoảng 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.

Ví dụ, nếu đầu vào là n = 108, thì đầu ra sẽ là True vì 108 = 14 + 94 (cả hai đều là bán số nguyên tố).

Các bước giải quyết:

MAX := 10000 (giả định đầu vào là tổng của các bán số nguyên tố trong phạm vi 1-10000).
nums := danh sách rỗng.
s_prime_flags := mảng kích thước MAX, khởi tạo False.
Định nghĩa hàm get_semi_primes() để tìm các bán số nguyên tố:
- Duyệt i từ 2 đến MAX-1:
  - count := 0, num := i, j := 2.
  - Trong khi count < 2 và j^2 <= num:
    - Trong khi num chia hết cho j: num := num / j, count := count + 1.
    - j := j + 1.
  - Nếu num > 1: count := count + 1.
  - Nếu count == 2: s_prime_flags[i] = True, thêm i vào nums.
Từ hàm chính:
- Gọi get_semi_primes().
- i := 0.
- Trong khi nums[i] <= n // 2:
  - Nếu s_prime_flags[n - nums[i]] là True, trả về True.
  - i := i + 1.
- Trả về False.

Xem ví dụ dưới đây để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

Đầu ra

True