BOJ 9020 골드바흐의 추측
5662 단어 2021.02.042021.02.04
https://www.acmicpc.net/problem/9020
시간 2초, 메모리 256MB
input :
- 테스트 케이스의 개수 T
- 짝수 n(4 ≤ n ≤ 10,000)
output :
- 주어진 n의 골드바흐 파티션을 출력
- 출력하는 소수는 작은 것부터 먼저 출력
조건 :
- 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력
오옹 잊고 있었는데 출력하는 소수는 작은 것 부터 하라고 했었네;;
별거 없다 가능 한 모든 소수를 찾아서 n을 만들 수 있는지 확인 하면 된다.
i, n - i 둘 다 소수인지를 판 별 해주어야 한다.
import sys
from math import sqrt
prime_number = [1] * 10001
prime_number[0] = prime_number[1] = 0
for i in range(2, int(sqrt(10001))):
for j in range(i * i, 10001, i):
if prime_number[j]:
prime_number[j] = 0
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
ret = []
for j in range(2, n // 2 + 1):
temp = n - j
if prime_number[j] and prime_number[temp]:
ret.append((j, n - j))
print(ret[-1][0], ret[-1][1])
Author And Source
이 문제에 관하여(BOJ 9020 골드바흐의 추측), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-9020-골드바흐의-추측저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)