检查整数是否可以表示为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()。这将需要

• 对于2到MAX-1范围内的i

• s_prime_flags [i]：=真

• 数：=数+ 1

• 虽然num可被j整除，但是

• j：= j + 1

• num：= num / j

• 数：=数+ 1

• 计数：= 0

• num：=我

• j：= 2

• 当count <2并且j ^ 2 <= num时

• 如果num> 1，则

• 如果计数等于2，则

• 在数字的末尾插入i

• 从主要方法中执行以下操作-

• 呼叫 get_semi_primes()

• i：= 0

• 而nums [i] <=（n / 2）的商，

• 返回True

• 如果s_prime_flags [n-nums [i]]为True，则

• 我：=我+ 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