백준 9020 풀이 (골드바흐의 추측 )

이번에는 "골드바흐의 추측"이라고 한다. 솔직히 난 문과출신이라 이런거 정의 보면 살짝 불편하다ㅋㅋㅋㅋ

그래도 정의가 어렵지는 않다.

큰 짝수는 반드시 두 소수로 나타낼 수 있다는 소리다. 그래서 N값에 대해서 두 소수를 구하면된다.

단, 두 소수의 차이가 가장 작아야한다. 그래서 시나리오를 짜봤다.

 

1. 소수리스트를 먼저 구한다.("에라토스테네스의 체"를 활용한다. 저번 포스팅에 이런방식으로 푸는 고수들이 있길래 따라했다.)

2. 짝수는 나누었을때 소수를 바로 가질수도 있고 하나씩 줄여가며 구해야할수도 있다.

3. 빼고자 하는 수가 소수인지, 뺀후에도 소수인지 판별한다.

4. 둘다 소수이면 출력

여기서 포인트는 빼고자 하는 수를 N/2부터 비교해서 빼기 시작한다는 것이다. line 13

def isPrime(num):
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return 0
    return 1*(num!=1)

tmp = []
for i in range(2,10000):
    if  isPrime(i):
        tmp.append(i)
case = int(input())
for _ in range(case):
    n = int(input())
    for i in range(int(n/2),1,-1):
        if i in tmp:
            if (n - i) in tmp:
                print(str(i) + " " + str(n-i))
                break