파이썬 백준 9020 골드바흐의 추측

def prime(n) :     if n < 2 :         return False     for j in range(2, n//2+1) :         if n%j == 0 :             return False     return True primelist = [] for i in range(10000) :     if prime(i) :         primelist.append(i)         testcase = int(input()) for j in range(testcase) :     n = int(input())     for i in range(n//2+1) :         a = n//2 - i         b = n//2 + i         if a in primelist and b in primelist :             print(a, b, sep = ' ')             break

1. 소수면 T, 소수가 아니면 F를 출력하는 함수 prime(n) 정의

2. 인풋받은 n을 반으로 잘라 ±i씩 for문으로 돌려가며 둘 다 소수인지 확인하며

3. 소수쌍이 발견되면 프린트하고 for문 break

 

첫 제출때 시간초과가 나와서 prime(n)의 for문에서 무의미한 절반을 날렸지만 그래도 시간초과가 나왔다.

주어진 range 내의 모든 소수를 미리 구해서 list에 저장하고, 소수쌍을 찾는데에는 prime(n)을 사용하지 않고 list만 참고하니 시간초과가 해결되었다.

range가 10,000으로 제한되어 있으니 소수list를 작성하는 과정을 에라토스테네스의 체를 이용해도 될 것 같다.

2부터 시작되는 list에서 쭉 훑으면서 자신의 배수를 list에서 날리면 되니 뒤로갈수록 훨씬 빨라질거고, 10000개의 수에 대해 자신의 절반만큼 for문을 돌리는 지금보다는 아마 그게 훨씬 빠를듯