백준 9020번 풀이 (+응용편)

문제

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

4 이상의 짝수에 대해 골드바흐 추측을 만족하면서 두 소수간 차이가 가장 작은 수를 출력하시오.

 

Reference

https://deokkk9.tistory.com/20

[python 파이썬] 백준 9020번: 골드바흐의 추측

https://github.com/tsamoglou/Goldbach-s-Weak-Conjecture/blob/master/PrimeNumbers.py

GitHub - tsamoglou/Goldbach-s-Weak-Conjecture: https://www.reddit.com/r/dailyprogrammer/comments/8bh8dh/20180411_challenge_356_i

(아래쪽은 응용편 참고문헌)

 

풀이

일단 골드바흐의 추측은 두 개가 있는데, 하나는 강한 추측이고 다른 하나는 약한 추측이다.

2보다 큰 모든 짝수는 소수 두 개의 합으로 정의할 수 있다.

골드바흐

이게 강한 추측(문제에 나오는 것)

5보다 큰 모든 홀수는 소수 세 개의 합으로 정의할 수 있다.

골드바흐

이게 약한 추측이다.

그래서 이게 무슨 소리냐고? 12=5+7일 때 5와 7은 소수다. 14=7+7일 때 7은 소수다. 7=2+2+3일 때 2와 3은 소수다. …뭐 그런 얘기다. 여기서 문제는 골드바흐의 강한 추측을 만족하는 순서쌍(중 두 소수간 차가 가장 작은 것)을 출력하는 것.

4 = 2+2
6 = 3+3
8 = 3+5
10 = 3+7 = 5+5
12 = 5+7
14 = 3+11 = 7+7
16 = 3+13 = 5+11
18 = 5+13 = 7+11
20 = 3+17 = 7+13
22 = 3+19 = 5+17 = 11+11
24 = 5+19 = 7+17 = 11+13
26 = 3+23 = 7+19 = 13+13
28 = 5+23 = 11+17
30 = 7+23 = 11+19 = 13+17
32 = 3+29 = 13+19
34 = 3+31 = 5+29 = 11+23 = 17+17
36 = 5+31 = 7+29 = 13+23 = 17+19
38 = 7+31 = 19+19
40 = 3+37 = 11+29 = 17+23
42 = 5+37 = 11+31 = 13+29 = 19+23
44 = 3+41 = 7+37 = 13+31
46 = 3+43 = 5+41 = 17+29 = 23+23
48 = 5+43 = 7+41 = 11+37 = 17+31 = 19+29
50 = 3+47 = 7+43 = 13+37 = 19+31

4부터 50까지 골드바흐 추측을 만족하는 순서쌍이 이렇게 있는데, 잘 보면 쌍이 하나인 것도 있고 여러개인 것도 있다. 저 여러개인 것들 중, 소수간 차이가 제일 적은 것… 그러니까 맨 뒤에 있는 걸 출력하면 된다.

 

본편 풀이

import sys
T = int(sys.stdin.readline())
def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

prime = []
for i in range(4,10001):
    if isprime(i):
        prime.append(i)

이것도 범위가 있는게… 쌩으로 돌리면 응애 나 애기시간초과! 가 반길 것 같으니 리스트부터 만들어보자…

for i in range(T):
    N = int(sys.stdin.readline())
    for j in prime:
        if j < N:
            print(j)

그리고 이렇게 하면 일단 N보다 작은 소수가 다 나오긴 한다. 근데 우리가 출력하는 형식이 n m이잖아요?

for i in range(T):
    N = int(sys.stdin.readline())
    for j in prime:
        if j < N and N - j in prime:
            print(j,N-j)

근데 또 이렇게 하면 모든 순서쌍…이 중복으로 나온다. 8을 입력하면 3 5와 5 3이 나오는데 우리는 앞에 있는 수가 더 작은 순서쌍만 볼거임…

for i in range(T):
    N = int(sys.stdin.readline())
    for j in prime:
        if j < N and N - j in prime and j < N - j:
            print(j,N-j)

아, 저거 저렇게 하면 10이 5 5가 아니라 3 7만 나온다… 그리고 저 중에서 가장 차이가 작은 쌍을 출력하려면 또 뭘 어떻게 해야 하는거냐고…OTL

for i in range(T):
    N = int(sys.stdin.readline())
    a = N // 2
    b = a
    while a > 0:
        if a in prime and b in prime:
            print(a,b)
            break
        else:
            a -= 1
            b += 1

하던 찰나에 저걸 찾은 것이다.

 

예를 들어서 8을 입력했다 치면, a와 b는 4가 된다. 그런데 4는 소수가 아니기때문에 목록에 없다. 그러면 a는 1을 빼고, b는 1을 더한 다음 둘 다 소수인지 확인한다. 그리고 둘 다 소수면? Profit!

import sys
T = int(sys.stdin.readline())
def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

prime = []
for i in range(1,10001):
    if isprime(i):
        prime.append(i)

for i in range(T):
    N = int(sys.stdin.readline())
    a = N // 2
    b = a
    while a > 0:
        if a in prime and b in prime:
            print(a,b)
            break
        else:
            a -= 1
            b += 1

그래서 이렇게 내면 맞는다. 시간제한이 촉박하다 싶으면 반복문은 빼거나 최소한의 범위로만 할 수 있게 셋업해주는 게 좋을 듯 하다.

 

응용편-골드바흐의 약한 추측

역시 미쿡이야… 어지간한건 다 해봤어… 대단함…

import sys
def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

N = int(sys.stdin.readline())
for i in range(2,N + 1):
    if isprime(i):
        for j in range(i,N - i):
            if isprime(N - i - j) and N - i + j == N:
                print(i,j,N - i - j)

위에 함수파트는 똑같이 가면 된다. 아래쪽이… i가 소수고 i부터 N-i까지 중에서 N-i-j가 소수이고 N-i+j가 N이랑 같으면… 모르것다… 일단 출력 결과물을 보면서 얘기해보자.

9
2 2 5
3 3 3

9를 넣었을 때 어떻게 되는가?

1. i가 2부터 10까지인데(사실상 9) 2가 isprime을 돌려보니까 소수여
2. 아따 그니까 j의 범위가 2에서 6까지(7 미만)인디
3. 이 때 N-i-j는 9-2-2인 5다. 그리고 5가 isprime이고 N-i+j는 9-2+2니까 9다.

출(별)력. 이게 1차 루프다.

1. i가 3일때 3은 소수니까 isprime을 패스하고
2. j의 범위는 3부터 5까지(6 미만)인데
3. 9-3-3이 3인디 3이 소수여… 그리고 9-3+3은 9여.

그래서 이렇게 된 거다. 252는 9-2+5가 9가 아니라 뺐나… 혹시 설명을 봐도 이해가 안되면…

https://pythontutor.com/visualize.html#mode=display

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java

여기서 한번 돌려보면 좋음. 참고로 저기는 임포트가 안돼서 sys.stdin.readlinne()을 input()으로 바꿔야 한다. 아 그럼 4는 어디갔냐고? 4는 합성수임다. 5는? 5는 range가 성립이 안된다. (5부터 4 미만이 뭐여)