Kiểm tra xem một số nguyên có thể được biểu thị dưới dạng tổng của hai số bán nguyên tố trong Python hay không

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

Như chúng ta biết bán nguyên tố là một số nếu nó có thể được biểu diễn dưới dạng tích của hai số nguyên tố. Một số bán nguyên tố đầu tiên là (phạm vi 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ì vậy, nếu đầu vào là n =108, thì đầu ra sẽ là True vì đây là tổng của 14 và 94 cả hai đều là bán nguyên tố.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MAX:=10000 giả sử các đầu vào đã cho là tổng các số bán nguyên tố nằm trong phạm vi từ 1 đến 10000
• nums:=một danh sách mới
• s_prime_flags:=một mảng có kích thước MAX và điền bằng False
• Xác định một hàm get_semi_primes (). Điều này sẽ mất
• đối với tôi trong phạm vi 2 đến MAX - 1, thực hiện
  • số lượng:=0
  • num:=i
  • j:=2
  • while count <2 và j ^ 2 <=num, do
    • trong khi num chia hết cho j, do
      • num:=num / j
      • count:=count + 1
    • j:=j + 1
  • nếu num> 1, thì
    • count:=count + 1
  • nếu số đếm giống như 2, thì
    • s_prime_flags [i]:=True
• chèn i vào cuối nums
• Từ phương thức chính, hãy làm như sau -
• gọi get_semi_primes ()
• i:=0
• while nums [i] <=quotient of (n / 2), do
  • nếu s_prime_flags [n - nums [i]] là True, thì
    • trả về True
  • i:=i + 1
• trả về Sai

Hãy cùng chúng tôi xem cách triển khai sau để 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]] == True:
         return True
      i += 1
   return False
n = 108
print(solve(n))

Đầu vào

[4, 2, 3], 11

Đầu ra

True