[백준] 9020번 문제 (골드바흐의 추측) 파이썬(Python) 풀이

문제 내용

# 골드바흐의 추측
import sys

def getPrime(num):
    primeList = []
    for i in range(2, num):
        isPrime = True
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            primeList.append(i)
    return primeList

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    primeList = getPrime(n)
    check = []
    if int(n / 2) in primeList:
        print("%d %d" % (n/2, n/2))
    else:
        for a in primeList:
            if n - a in primeList:
                if abs((n-a)-a) not in check:
                    check.append(abs((n-a)-a))
                else:
                    print(n-a, a)
                    break

내가 작성한 코드는 이렇다..

 

우선 getPrime 함수는 입력된 숫자 n에 대하여 2랑 같거나 크고 n보다 작은 소수를 찾아 리스트 형태로 리턴한다.

굳이 n까지 소수인지 아닌지 체크를 안 한 이유는 n은 어차피 짝수라 소수가 아니기 때문이다.

 

그 후 밑에 코드부터는 getPrime 함수로 받아온 소수 리스트들에 있는 숫자 두개를 더하여 n을 만드는 내용인데

    if int(n / 2) in primeList:
        print("%d %d" % (n/2, n/2))

 이 부분은 만약 n / 2를 한 숫자가 primeList안에 있다면 제일 적은 차이의 소수일 것이다.

 

예를 들어 숫자 10이 n으로 들어오면 10사이에 있는 소수는 [2, 3, 5, 7]일 것인데 5와 5를 더하면 10이 되고 두 수 5, 5의 차는 0이기 때문에 두 소수끼리 제일 적은 차이를 가진다.

 

그 외는 

    else:
        for a in primeList:
            if n - a in primeList:
                if abs((n-a)-a) not in check:
                    check.append(abs((n-a)-a))
                else:
                    print(n-a, a)
                    break

이런 코드인데 만약 n - a가 소수리스트인 primeList에 있다면 적어도 조합을 통해 숫자 n을 만들 수 있다는 이야기가 되고..

그 이후 거기서 제일 적은 차이의 숫자를 알기 위해 check리스트에 n-a와 a간의 차를 더해주다가 만약 check에 들어가 있는 숫자들 중에 n-a와 a간의 차가 이미 존재하는 경우를 파악했다.

 

뭔가 말을 너무 어렵게 한 거 같은데 ..

 

이게 무슨 소리나면..

 

예를 들어 n이 16이면

primeList는 [2,3,5,7,11,13]이 되는데

16이 되는 조합은 

3 13

5 11

11 5

13 3이 된다.

 

그러면 순서대로 check는 

3 - 13의 차의 절대값인 10이 리스트에 들어가고 => [10]

5 - 11의 차의 절대값인 6이 리스트에 들어가고 => [10, 6] 

11 - 5의 ... 하면 [10, 6, 6]이 들어가는데 이 경우가 앞서 들어간 6과 같은 숫자가

들어가게 되는 경우고 이 경우의 숫자 11, 5의 숫자가 자연스럽게 숫자끼리 차이가 가장적은 숫자가 된다..