Python 中檢查整數是否可以表示為兩個半素數之和

假設我們有一個數字 n，我們需要檢查 n 是否可以表示為兩個半素數之和。

眾所周知，半素數是指可以表示為兩個素數乘積的數。前幾個半素數（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。

因此，如果輸入為 n = 108，則輸出為 True，因為它是 14 和 94 的和，這兩個數字都是半素數。

為了解決這個問題，我們將遵循以下步驟：

• MAX := 10000，假設給定的輸入是 1 到 10000 範圍內半素數的和
• nums := 一個新列表
• s_prime_flags := 一個大小為 MAX 的陣列，並填充為 False
• 定義一個函式 get_semi_primes()。它將接收
• 對於 i 從 2 到 MAX - 1，執行以下操作：
  • count := 0
  • num := i
  • j := 2
  • 當 count < 2 且 j^2 <= num 時，執行以下操作：
    • 當 num 可以被 j 整除時，執行以下操作：
      • num := num / j
      • count := count + 1
    • j := j + 1
  • 如果 num > 1，則
    • count := count + 1
  • 如果 count 等於 2，則
    • s_prime_flags[i] := True
• 將 i 插入到 nums 的末尾
• 從主方法執行以下操作：
• 呼叫 get_semi_primes()
• i := 0
• 當 nums[i] <= n / 2 的商時，執行以下操作：
  • 如果 s_prime_flags[n - nums[i]] 為 True，則
    • 返回 True
  • i := i + 1
• 返回 False

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

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

輸入

[4, 2, 3], 11

輸出

True

Arnab Chakraborty

更新於: 2020-12-30

591 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習