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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习