[백준] 17103번 (python 파이썬)

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

import sys

arr = [True]*1000001
arr[0] = arr[1] = False

for i in range(2, 1001):
  if arr[i]:
    for j in range(i+i, 1000001, i):
      arr[j] = False

testcase = int(sys.stdin.readline())
for _ in range(testcase):
  number = int(sys.stdin.readline())
  count = 0
  m = number // 2 + 1
  for i in range(2, m):
    if arr[i] and arr[number-i]:
      count += 1
  print(count)

 

미리 입력 최대값인 백만까지의 소수 리스트를 만들어 놓고 한다.

하지만, 백만은 어디까지나 입력 범위 최대의 수이므로 실제 입력한 값까지의 소수 리스트만 만들어도 된다.

import sys

testcase = int(input())
nums = [int(sys.stdin.readline()) for _ in range(testcase)]
m = max(nums)
arr = [True] * (m+1)
arr[0] = arr[1] = False

k = int(m ** 0.5) + 1
for i in range(2, k):
  if arr[i]:
    for j in range(i+i, m + 1, i):
      arr[j] = False

for num in nums:
    result = 0
    for i in range(2, num // 2 + 1):
        if arr[i] and arr[num - i]:
            result += 1
    print(result)