[백준] 9020번-골드바흐의 추측 (Python) -> 소수찾기의 극한

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

제한

• 4 ≤ n ≤ 10,000

예제 입력 1 

3
8
10
16

예제 출력 1 

3 5
5 5
5 11

 

소수? -> 에라토스테네스의 체! 

이 문항은 에라토스테네스의 체를 잘 활용해서 해결하는 문제인데 약간 최종 보스까진 아니더라도 약간 뭔가 배운 것들을 많이 동원한 문항이었음. -> 그리고 김태윤씨가 이런 문항 프원실인가? 나중에 가면 '소수 찾기'같은 문항 많이 푼다고 그러셔서 따로 정리할 필요가 있음을 느꼈는데 특히 이 문항이 가장 인상깊었기 때문에 올리도록 하겠음.

 

풀이

Step 1) 소수 list를 미리 만들어버려라. ->차피 range가 10000이라 미리 소수 리스트를 만드는 것이 연산속도 빠름

Step 2) 풀이법 고민해보자!

 

 

Step 1 소수 list를 만드는 방법

소수만을 list로 만들면 나중에 코드짜기 굉장히 번거롭기 때문에 해당 리스트 index값이 소수인지 아닌지 True, False로 만들어버림. 소수면 True, 아니면 False로 함.

 

import sys
import math

sosu = [True for _ in range(10000 + 1)]

sosu[0], sosu[1] = False, False
for i in range(2, int(math.sqrt(10000) + 1)):
    if sosu[i]:
        j = 2
        while i * j <= 10000:
            sosu[i * j] = False
            j += 1

이 코드가 소수 list코드인데 일단 0~10000번째에 True를 넣어버렸고, 0과 1은 소수가 아니기 때문에 바로 False로 바꿔줌.

여기서 2가 소수이기 때문에 2의 배수를 모두 False로 바꿔줬고 같은 방식으로 j+1을 해서 각자의 배수를 다 False로 바꿔버림. 그러면 알아서 걸러졌음.

근데 여기서 중요한게 range였다. (어쩌면 '시간'을 줄이기 위한 가장 중요한 포인트같기도..?) 여튼 그래서 range(2,int(math.squrt(10000)+1)) 이 부분이 가장 괜찮았던 것 같다. 1이 아니라 2인 이유는 2,3,5,7,11같은 숫자들은 i*j를 했을 때 만약에 j가 1부터 시작될 경우 소수임에도 불구하고 억울하게 False로 바뀔 것이기 때문이며, 아무튼 그러하고!

If sosu[i]를 활용한 부분이 좋은데 왜냐하면 이미 False로 dominate 된 부분이 while문으로 쫙 돌아가버리면.. 시간이 매우 매우 소모되기 때문이고 True, False로 채워놓은 보람이 있게끔 만들어 줄 수 있었음.

 

Step 2 풀이법

이번 문제의 사실 목적...이라 해야할지 이 문제를 특별하게 만들어준 질문임.

일단 조건이 포인트인데, input에 들어가는 수가 짝수이다!

그럼 일단, ans에 //2값을 두번 append해줘보면 된다. 그러면 얼떨결에 22같은 경우나 46같은 수는 기깔나게 답이 나온다. 그러나 아닐 경우에는 어떻게하냐? 그러면 ans[0]-=1;ans[1]+=1을 whlie문을 돌려서 해주면 된다.

이때 while문의 조건이 기깔나는데 이유는 True False 문을 활용하여 소수를 찾았기 때문에 굉장히 굉장히 쉽게 짜여질 수 있다. 

for _ in range(int(input())):
    num = int(sys.stdin.readline())
    ans = [num//2 for _ in range(2)]

    while True:
        if sosu[ans[0]] and sosu[ans[1]]: break
        else:
            ans[0] -= 1
            ans[1] += 1

    print(*ans)

그러면 위와 같이 굉장히 아름답게 나온다.

 

최종코드는?

import sys
import math

sosu = [True for _ in range(10000 + 1)]

sosu[0], sosu[1] = False, False
for i in range(2, int(math.sqrt(10000) + 1)):
    if sosu[i]:
        j = 2
        while i * j <= 10000:
            sosu[i * j] = False
            j += 1

for _ in range(int(input())):
    num = int(sys.stdin.readline())
    ans = [num//2 for _ in range(2)]

    while True:
        if sosu[ans[0]] and sosu[ans[1]]: break
        else:
            ans[0] -= 1
            ans[1] += 1

    print(*ans)