반응형
https://www.acmicpc.net/problem/9020
9020번: 골드바흐의 추측
문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
www.acmicpc.net
prime_list = [False, False] + [True]*10002
for i in range(2, 10002):
if prime_list[i]:
for j in range(2*i, 10002, i):
prime_list[j] = False
T = int(input())
for i in range(T):
n = int(input())
a = n//2
b = a
while a>0:
if prime_list[a] and prime_list[b]:
print(a, b)
break
else:
a-=1
b+=1
먼저 문제에서 주어진 범위의 모든 소수를 에라스토테네스의 체를 이용하여 구했다. 그리고 가능한 골드바흐의 파티션이 여러 가지인 경우 두 수의 차가 적은 수를 구하는 것이므로 입력받은 n의 중간부터 비교해 나갔다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [python 파이썬] 백준 3009번: 네 번째 점 (0) | 2020.01.10 |
|---|---|
| [python 파이썬] 백준 1085번: 직사각형에서 탈출 (0) | 2020.01.09 |
| [python 파이썬] 백준 1929번: 소수 구하기 (2) | 2020.01.02 |
| [python 파이썬] 백준 2581번: 소수 (0) | 2019.12.31 |
| [python 파이썬] 백준 1978번: 소수 찾기 (0) | 2019.12.30 |
