[Python] 6588번 : 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

문제 3줄 요약

1. 수백년 전, 골드바흐는 추측했다.

2. "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다."

3. 백만 이하의 모든 짝수에 대해 검증해봐라

 

 

---

 

8은 3 + 5 로 나타낼 수 있다.

42는 나타낼 수 있는 경우가 많은데,

만들 수 있는 방법이 여러 가지인 경우는 두 수의 차가 가장 큰 것을 출력한다.

 

또한

소수의 합으로 나타낼 수 없다면,

문자열을 출력하라는데

없는 경우가 있을까...?

 

문제에서 N은 최대 100만이지만,

이미 그 이상의 넓은 범위까지도 참이라는 것은 증명됐다고 한다.

 

여튼!

소수이기 때문에

에라토스테네스의 체가 빠질 수 없다.

 

에라토스테네스의 체가 뭐지?

라는 생각이 든다면,

아래 링크를 확인해보자!

 

2023.02.22 - [프로그래밍 공부/백준 알고리즘] - [Python] 1644번 : 소수의 연속합

[Python] 1644번 : 소수의 연속합

 

---

필요한 소수부터

에라토스테네스의 체를 이용하여 구해두자

 

에라토스테네스의 체를 짧게 설명하자면,

모든 정수를 나열해놓고 소수의 배수들을 빼나가면서,

소수만 남겨놓는 방식으로 소수를 찾는다.

 

코드로 작성해보면,

from sys import stdin

# max : 최대 N인 100만
# num_list : 소수를 담을 리스트
# visited : 소수인지 아닌지 체크할 리스트, 0과 1은 소수가 아니다.
max, num_list, visited = 1000000, [], [True]*1000000
visited[0],visited[1] = False,False

# 2부터 max의 제곱근까지 소수 판정을 한다.
for num in range(2, int(max**0.5)):
    if visited[num] == False:
        continue
    num_list.append(num)

	# max 이하인 모든 배수들 소수 제외
    check = 2
    while(check*num < max):
        visited[check*num] = False
        check += 1

 

여기서 소수 판정 시,

2 부터 max의 제곱근까지만 반복문을 돌리는 것을 볼 수 있다.

 

max가 10이라고 가정하고,

1 ~ 10 안의 소수를 구해보면 아래와 같을 것이다.

2인 경우, [ 4, 6, 8, 10 ] - 소수 제외

3인 경우, [ 3, 6, 9 ] - 소수 제외

5인 경우, [ 5, 10 ] - 소수 제외

 

남은 2, 3, 5, 7이 소수가 되겠다.

하지만 여기서 5일 경우에서 10은 이미 2인 경우에서 제외가 되었으므로,

굳이 방문하지 않아도 될 정수인 것이다.

 

따라서,

max 10의 제곱근인 3까지만 탐색을 한다.

 

사소해보이겠지만,

숫자가 어마어마하게 커진다면

제곱근으로 줄인다는 것이 시간복잡도에서는 매우 크다!

 

---

 

이제 남은건

"소수의 합으로 나타낼 수 있냐" 이다.

 

투 포인터로 소수 리스트의

두 개의 값 합을 N의 근사치로 찾아가려고 했으나,

8%에서 시간 초과가 발생하였다.

 

다시 생각해보니

이미 소수인지 아닌지 visited 리스트에 판별을 해놨으니,

N = A + B 라면,

N = A + (N - A)로 볼 수 있다.

 

따라서

A가 소수이고, (N-A)도 소수라면,

탐색 종료!

 

from sys import stdin

# max : 최대 N인 100만
# num_list : 소수를 담을 리스트
# visited : 소수인지 아닌지 체크할 리스트, 0과 1은 소수가 아니다.
max, num_list, visited = 1000000, [], [True]*1000000
visited[0],visited[1] = False,False

# 2부터 max의 제곱근까지 소수 판정을 한다.
for num in range(2, int(max**0.5)):
    if visited[num] == False:
        continue
    num_list.append(num)

	# max 이하인 모든 배수들 소수 제외
    check = 2
    while(check*num < max):
        visited[check*num] = False
        check += 1

# 소수의 합으로 나타낼 수 있는지 판정
while(True):
    N = int(stdin.readline())
    if N == 0:
        break

	# N = first + (N - first)
    # first, (N - first) 모두 소수라면, 종료
    for first in range(2, max):
        if visited[first] and visited[N-first]:
            print(f"{N} = {first} + {N-first}")
            break

 

골드바흐의 추측..

이 다음 문제에서도 유용하게 사용되는데

to be continue..