[백준] 9020 .py - 골드바흐의 추측

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

n = int(input())
result =[ list() for _ in range(n) ]
max_num=2
for i in range(n):
    x = int(input())
    if x % 2 == 0:
        result[i].append(x)
    else:
         del result[i]
    if max_num<x:
        max_num=x
#print("result",result)


#에라토스테네스의 체 - 시간초과 문제 해결을 위해
def primeCheck(x):
    for i in range(2,x):
        if x%i==0:
            return False
    return True


first_primes=[i for i in range(2,int(max_num**(1/2))) if primeCheck(i)]
primes=first_primes.copy()
for i in range(first_primes[-1]+1,max_num):# 11의제곱은 100 초과.
    # 100이하의 11의 배수는 저 소수들의 곱셈일 수밖에
    for p in first_primes:
        if (i%p==0) :
              break
        elif p==first_primes[-1]:
                primes.append(i)
#print("primes",primes)


#골드바흐의 추측
def search(n):
    global primes
    n//=2
    #print(n)
    for i in range(len(primes)): 
        if primes[i]>n:
            return i-1
    #return 0

for num in result:
    if num[0]/2 in primes:
        num.append(int(num[0]/2))
        num.append(int(num[0]/2))
        print(int(num[0]/2), int(num[0]/2))
    else:
        idx = search(num[0])
        #print(idx)
        left, right = idx, idx+1
        while primes[left]+primes[right] != num[0]:
            if primes[left]+primes[right] < num[0] and right<len(primes)-1:
                right += 1
            elif primes[left]+primes[right] > num[0] and left>0:
                left -= 1
            #print(left, right,"흠")
            #left = primes[idx-1]
            #right = primes[idx]
        num.append(primes[left])
        num.append(primes[right])

        print(primes[left], primes[right])
#print(result)