9020 골드바흐의 추측

골드바흐 추측이란
 > 2보다 큰 짝수는 모두 소수의 합으로 나타낼수 있다는 추측이다 .. 그렇다 추측이다 아직 증명하지 못한!
   하지만 범위를 한정하면 어느정도 구할 수 있다

 

 

.. 문제에서 소수가 들어간다 ...

배운걸 써먹어야한다 ..

1. 에라토스테네스의 체 를 사용해야한다 !

 > 이와 관련해 팀원에게 들은 정보는. 이런 문제는 체를 미리 만들어 놓는것이지.. 체만드는 것을 함수로 호출해서 매번 체를 만드는 것이 아니다 ...!

2. 이왕 만든 에라토스테네스의 체를 잘이용하자! 시간을 단축 시킬 . 수있다. ! 

 

내가 생각한 골드만의 추측에 해당되는 골드바흐 파티션을 모두 배열에 담아서 리턴시켜주는 함수이다 .

def gold(n:int)->list:
    prim_l=prim_list(n) # prim_list는 에라체 만드는 함수
    arr=[]
    return_list=[]
    for i in prim_l:
       for j in prim_l:
            if a-j-i==0:
                arr=[i,j]
                return_list.append(arr)
                break;
    return return_list

나름 break를 통해 시간을 감소시켰다고 생각했지만 시간초과가 나왔다.

 

결국 이중 루프를 해결 할 방안을 모색해야했는데 팀원이 귀뜸을 줬다...

짝수 N에서 소수를 빼서 나머지가 소수인지 판별하면 좀더 단축시킬 . 수있다는...

 

추가로 n/2 까지만 판별해서 중복되는 파티션 조합을 제외 시켰다,

---

prime_list = [True]*10000
prime_list[0] = False
prime_list[1] = False
for i in range(2,10000):
    if prime_list[i]:
        j=2
        while i*j <10000:
            prime_list[i*j] = False
            j+=1
def gold(n):
    return_list=[]
    for i in range(2,(n//2)+1):
        arr = []
        if prime_list[i]:
            a=n-i
            if prime_list[a]:
                arr.append(i)
                arr.append(a)
                return_list.append(arr)
    return return_list

n= int(input())


for i in range(n):
    a=int(input())
    check_List=gold(a)
    min=check_List[0]
    for i in check_List[1:]:
        min_a=min[0]
        min_b=min[1]
        if (min_b-min_a)>i[1]-i[0]:
            min=i
    print(*min)