단계별풀기 - 기본수학2
# 9020 골드바흐의 추측 (실버1)
- 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
- 각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
- 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
- point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기
- prime 값이 True면 소수
- point. 두 소수의 차이가 가장 작은것을 출력한다 & 작은 소수부터 출력한다 -> 중간값부터 확인해본다
- n = 8 이면 4,4 -> 3,5(break) -> 2,6 -> 1,7 순으로 확인
- n = 10 이면 5,5(break) -> 4,6 -> 3,7 -> 2,8 -> 1,9 순으로 확인한다.
- n = 16 이면 8,8, -> 7,9 -> 6,10 -> 5,11(break) -> ...
def isprime(n):
n += 1
prime = [True] * n # n개의 [True]가 있는 리스트 생성
for i in range(2, int(n ** 0.5) + 1): # n의 제곱근까지만 검사
if prime[i]: # prime[i]가 True일때
for j in range(2 * i, n, i): # prime 내 i의 배수들을 False로 변환
prime[j] = False
return prime
for _ in range(int(input())):
n = int(input())
prime_list = isprime(n)
half = n//2
for i in range(half, 1, -1):
if prime_list[i] and prime_list[n-i]:
print(i, n-i)
break
반응형
'알고리즘 > baekjoon' 카테고리의 다른 글
20210126_코테공부 (0) | 2021.01.26 |
---|---|
20210125_코테공부 (0) | 2021.01.25 |
20210121_코테공부 (0) | 2021.01.21 |
20210120_코테공부 (0) | 2021.01.20 |
20210119_코테공부 (0) | 2021.01.19 |