백준 알고리즘
[백준/Python] 9020_골드바흐의 추측
헝그리개발자
2021. 7. 1. 20:50
문제
https://www.acmicpc.net/problem/9020
9020번: 골드바흐의 추측
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아
www.acmicpc.net
풀이
에라토스테네스의 체를 사용합니다.
https://steadycode.tistory.com/51
[알고리즘] 에라토스테네스의 체
에라토스테네스의 체란 수학에서 소수를 찾는 방법입니다. 대량의 소수를 찾아야할 때 효과적이며, 소수를 직접 찾는 것이 아니라 일정 범위를 정해놓고 소수가 아닌 수를 지워나가는 것에 가
steadycode.tistory.com
10000까지 소수를 판별한 배열을 구합니다.
매 테스트마다 n // 2부터 2까지 탐색합니다.
그 중 가장 먼저 나온 골드바흐 파티션의 값이 두 소수의 차이가 가장 작은 골드바흐 파티션입니다.
코드
import sys
prime = [True] * 10001
prime[0], prime[1] = False, False
for i in range(2, int((10000 ** 0.5)) + 1): # 에라토스테네스의 체
for j in range(i * 2, 10001, i):
prime[j] = False
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
n = int(sys.stdin.readline().rstrip())
for i in range(n // 2, 1, -1): # 가장 먼저 나온 값이 두 소수의 값이 최소인 경우이다
if prime[n - i] and prime[i]:
print(i, n - i)
break # 골드바흐 파티션이 나오면 반복문 종료