Pythonで整数を2つのセミプライムの合計として表現できるかどうかを確認します

数がnであるとすると、nが2つの半素数の合計として表現できるかどうかを確認する必要があります。

私たちが知っているように、半素数は、2つの素数の積として表現できる場合は数です。最初のいくつかの半素数は（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の場合、これは14と94の合計であるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• MAX：=10000与えられた入力が、1から10000の範囲にあるセミプライムの合計であると仮定します
• nums：=新しいリスト
• s_prime_flags：=サイズMAXの配列で、Falseで埋める
• 関数get_semi_primes（）を定義します。これには時間がかかります
• 2〜MAX-1の範囲のiの場合は、
  • count：=0
  • num：=i
  • j：=2
  • count<2およびj^2 <=numの場合、do
    • numはjで割り切れますが、
      • num：=num / j
      • count：=count + 1
    • j：=j + 1
  • num> 1の場合、
    • count：=count + 1
  • カウントが2と同じ場合、
    • s_prime_flags [i]：=True
• 数字の最後にiを挿入
• メインの方法から次のようにします-
• get_semi_primes（）を呼び出す
• i：=0
• nums [i] <=（n / 2）の商である間、do
  • 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