백준 6588. 골드바흐의 추측 (Python)

문제 https://www.acmicpc.net/problem/6588

풀이

소수를 구하는 것이 핵심
에라토스테네스의 체를 이용해 100만이하의 소수를 구한다.(소수일경우 1, 아닐경우 0)
그리고 테스트케이스의 수를 고려해 input은 stdin.readline()를 이용!

• 테스트케이스 n를 입력받는다.
• 에라토스테네스를 통해 구해진 배열arr을 3부터 순회한다
  - 3부터 순회하는 이유는 2는 짝수이기때문에!(두 홀수인 소수의 합을 찾아야함)
• arr[i]과 arr[n-i]이 소수일경우 정답을 출력하고 소수배열순회 종료

from sys import stdin
arr=[1 for _ in range(1000001)]
for i in range(2,1001):
    if arr[i]:
        for j in range(i+i,1000001,i):
            arr[j]=0

while True:
    n=int(stdin.readline())
    b=0
    if n==0:break

    for i in range(3,len(arr)):
        if arr[i] and arr[n-i]:
            print(f'{n} = {i} + {n-i}')
            b=1
            break

    if b==0:
        print("Goldbach's conjecture is wrong.")

위 풀이는 python3 제출시, 시간초과이다.
pypy3로 제출시, 688ms로 통과!
아래코드는 개선한 코드이다.
소수배열을 순회하지만, 소수가 아닌 숫자가 더 많아 소수만 따로 담는 배열과 딕셔너리를 이용해 순회시간단축!
아래코드를 통해 python3 제출시, 1912ms, pypy3 제출시, 340ms

from sys import stdin
arr=[1 for _ in range(1000001)]
so=[]
dic={}
for i in range(2,1001):
    if arr[i]:
        for j in range(i+i,1000001,i):
            arr[j]=0

for i in range(3,1000001):
    if arr[i]==1:
        so.append(i)
        dic[i]=1

while True:
    c=int(stdin.readline())
    b=0
    idx=0
    if c==0:
    	break
    for i in range(len(so)):
        if c-so[i] in dic:
            print(f'{c} = {so[i]} + {c-so[i]}')
            b=1
            break
    if b==0:
        print("Goldbach's conjecture is wrong.")