17103번: 골드바흐 파티션
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
www.acmicpc.net
문제
- 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
문제풀이
#소수가 저장되는 리스트
prime = []
n=1000000
#에라토스테네스의 체
arr = [False, False] + ([True] * (n - 1)) #01
for i in range(2, n+1):
if arr[i]: #02
prime.append(i)
for j in range(i * 2, n, i): #03
arr[j] = False
ans=[] #04
for i in range(int(input())):
#05
a = int(input())
cnt=0
#06
for i in range(len(arr)):
if prime[i]>a-prime[i]:
break
#07
if arr[a-prime[i]]:
cnt+=1
#08
ans.append(cnt)
print(*ans, sep='\n')- prime은 소수를 저장할 리스트이다.
- 에라토스테네스의 체를 이용하여 n까지의 소수를 prime에 저장할 것이다.
- #01 : n개의 리스트를 만들어준다. 기본적으로 소수만 True, 비소수이면 False로 저장할 것이다.
초기값은 0,1을 제외한 2부터 n까지 모두 True로 저장을 한다.
- #02 : arr[i]가 소수인 경우 즉 True인 경우 prime에 값을 추가한다.
애초에 시작값 2는 소수이기에 바로 prime에 값을 추가해도 상관이 없다.
- #03 : if문이 끝나고 시작값 2(i)부터 n까지 2(i)의 간격으로 for문을 돌린다.
즉 2의 배수는 모두 소수가 아니므로, 모두 False로 값으로 바꿔준다.
해당 for문을 그 다음에는 3, 4, 5 ... n까지 늘려가며 prime 값에 소수를 추가해준다.
- #04 : 사실상 여기서부터 문제의 시작이다. 값을 출력할 ans 리스트를 만들어준다.
- #05 : 테스트의 개수와 각 테스트 값을 적당히 입력받고, cnt 즉 개수를 저장할 변수를 선언한다.
- #06 : for문을 arr의 길이만큼 반복한다.
처음 if문을 해석하자면 "소수>입력받은 값-소수"이면 멈춘다는 뜻이다.
즉 이 뜻은 골드바흐 파티션을 만족하기 위해서 "소수1+소수2=입력받은 값"을 이용하여,
"소수>입력받은 값-소수"이면 조건을 성립하지 않는다는 것이다.
- #07 : 이 if문도 "소수=입력받은 값-소수"을 이용하여 arr[입력받은 값 - 소수] 값이 소수(True)라면
해당 조건을 성립하기에 개수(cnt)에 1을 추가해준다.
- #08 : 입력받은 a의 조건을 성립하는 개수(cnt)를 ans에 추가해준다.
최종적으로 그 개수를 \n을 기준으로 출력해준다.
'프로그래밍 > 백준' 카테고리의 다른 글
| [알고리즘] 백준 1003 파이썬 - 피보나치 함수 (1) | 2022.11.20 |
|---|---|
| [알고리즘] 백준 15654 파이썬 - N과 M(5) (백트래킹) (1) | 2022.11.19 |
| [알고리즘] 백준 10974 파이썬 - 모든 순열 (0) | 2022.11.17 |
| [알고리즘] 백준 2606 파이썬 - 바이러스(DFS 풀이) (2) | 2022.11.16 |
| [알고리즘] 백준 8979 파이썬 - 올림픽 (0) | 2022.11.15 |