정수가 파이썬에서 두 반소수의 합으로 표현될 수 있는지 확인

숫자 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에 대해 다음을 수행합니다.
  • 카운트:=0
  • num :=나
  • j :=2
  • count <2 및 j^2 <=num, do
    • num이 j로 나누어지는 동안 do
      • num :=num / j
      • 카운트 :=카운트 + 1
    • j :=j + 1
  • 숫자> 1이면
    • 카운트 :=카운트 + 1
  • 카운트가 2와 같으면
    • s_prime_flags[i] :=사실
• 숫자 끝에 i 삽입
• 메인 방법에서 다음을 수행하십시오 -
• get_semi_primes() 호출
• i :=0
• while nums[i] <=(n / 2)의 몫, do
  • s_prime_flags[n - nums[i]]가 True이면
    • 참 반환
  • 나는 :=나는 + 1
• 거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

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