백준 알고리즘 9020번 골드바흐의 추측(python)

에라토스네테스의 체를 사용해야 하는 소수 문제이다. 첫번째 코드가 두 번째 코드가 2배 정도 빠르게 나오는데 왜 그런지 모르겠다... 두 번째 코드는 PyPy3로 제출하면 통과는 된다.

for _ in range(int(input())):
    n = int(input())
    li = [1]*(n+1)
    for i in range(2, int((n+1)**0.5) + 1):
        if li[i] == 1:
            for j in range(i+i, n+1, i):
                li[j] = 0
    ans_li = []
    for i in range(2, n//2+1):
        if li[i] == 1 and li[n-i] == 1:
            ans_li.append([i, abs(i-(n-i))])
    ans_li = sorted(ans_li, key=lambda x : x[1])
    print(ans_li[0][0], n - ans_li[0][0])

for _ in range(int(input())):
    n = int(input())
    li = [1]*(n+1)
    for i in range(2, int((n+1)**0.5) + 1):
        if li[i] == 1:
            for j in range(i+i, n+1, i):
                li[j] = 0
    prime = [i for i in range(2, n+1) if li[i]]
    ans_li = []
    for p in prime:
        if n-p in prime:
            ans_li.append([p, abs(p-(n-p))])
    ans_li = sorted(ans_li, key=lambda x : x[1])
    print(ans_li[0][0], n-ans_li[0][0])