백준-9020

• 골드바흐의 추측이라는 문제이다.
• 10000이하의 짝수는 두개의 소수의 합으로 나타낼 수 있다는 추측이다.

t=int(input())
a=[0, 0]+[1]*(9999)
primes=[]

for i in range(2, 10001):
    if a[i]:
        primes.append(i)
        for j in range(i*2, 10001, i):
            a[j]=0

for _ in range(t):
    n=int(input())
    ans=[]
    
    for i in primes:
        if i>n: break
        num=n-i
        if a[num]:
            ans.append([min(num, i), max(num, i)])

    Min, result=1000000, []
    for i in ans:
        if Min>(i[1]-i[0]):
            Min=i[1]-i[0]
            result=i
    for i in result:
        print(i, end=' ')
    print()
        

나는 위의 코드로 해결하였지만 시간이 굉장히 오래걸렸다.
에라토스테네스의 체를 이용하였지만 이는 그냥 소수를 구하는 과정일 뿐
그 아래에 짝수에서 소수를 뺀 값들을 다시 저장하는 과정과 두 수의 간격이 최소인 부분을
판별하는 과정에서 굉장히 시간이 오래걸린 것 같다.

그래서 다른 블로그를 찾아보니 아래와 같은 방법을 쓰고 있었다.

t=int(input())
lis=[0, 0]+[1]*(9999)

for i in range(2, 10001):
    if lis[i]:
        for j in range(i*2, 10001, i):
            lis[j]=0

for _ in range(t):
    n=int(input())
    
    a=n//2
    b=a
    while a>0:
        if lis[a] and lis[b]:
            print(a, b)
            break
        else:
            a-=1
            b+=1

lis는 인덱스 값이 소수라면 1이다. 따라서 a와 b는 lis 리스트의 중간부터 시작해서
좌우로 이동하면서 둘 다 해당 위치의 값이 1이라면 이는 둘 다 소수인 것이고 처음 확인된 위치는 당연히 간격이 가장 좁은 위치인 것이다.

어떻게 저런 생각을 하는지 좀 더 공부를 해야겠다...