코딩테스트 대비/단계별 코딩 테스트 준비(27일 과정)
[math3/Python] 9020번: 골드바흐의 추측 - 효과는 굉장했다!
bluetag_boy
2022. 2. 11. 20:36
반응형
9020번: 골드바흐의 추측
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아
www.acmicpc.net
알고리즘 분류
- 수학
- 정수론
- 소수 판정
- 에라토스테네스의 체
SOLUTION
import sys
sosu = [0 for i in range(10001)]
sosu[1] = 1 # 0 = 소수, 1 = 소수가 아닌 수
for i in range(2,101): # 제곱근까지만 탐색하면 되므로 10001 의 제곱근인 100 까지
for j in range(i+i, 10001, i): # i의 배수들은 전부 소수가 아니므로 제외시킴
sosu[j] = 1 # i + i 인 이유? 첫번쨰 i는 소수가 될 수 있기 때문에
T = int(sys.stdin.readline())
for _ in range(T):
n = int(sys.stdin.readline())
half_n = n // 2
for j in range(half_n, 1, -1):
if sosu[n-j] == 0 and sosu[j] == 0: # n의 절반에서 부터 탐색시작 두 소수의 차이가 가장 적게 만들기 위해
print(j, n-j)
break