백준 17103 문제 풀이 python

🐒 골드바흐 파티션

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

✍ 나의 풀이

import sys

t = int(input())

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

for _ in range(t):
    result = 0
    n = int(sys.stdin.readline().rstrip())

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

제출할때마다 왜 시간초과가 나오나 했는데 지금까지 에라토스테네스의 체를 반복문 안에서 계속 만들고 있었다..

---

🧠 문제 이해

골드바흐의 추측 응용문제이다.

2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

1. 에라토스테네스의 체를 이용해 주어진 정수까지의 소수를 찾아내고
2. 주어진 정수를 소수들의 합으로 나타낼 수 있는 가짓수를 출력해야한다.

에라토스테네스의 체는 한번 만들어놓고 여러번 사용할 수 있을때 쓰는게 시간적으로 효율적인 것 같다.