[백준/BEAKJOON] 17103번 골드바흐 파티션

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

 

문제

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

 

https://na0-0.tistory.com/107

위의 문제와 유사하게 해결할 수 있다. 100만 이하의 수에 대해, 에라토스테네스의 체로 모든 소수를 찾아서 table list에 저장해놓은 다음에 확인을 해주는 작업을 진행한다.

 

문제 해결 프로세스

- 두 소스의 합으로 짝수를 이루는 과정에서, 각 수가 소수인지 학인

- 테스트케이스가 여러번 주어지기 때문에, 각 수에 대해서 소수인지 체크하는 리스트를 만들어놓으면, 공통으로 사용할 수 있다.

- 소수인지 아닌지 확인하는 과정에서 에라토스텐네스의 체를 활용한다.

 

2보다 큰 짝수 n은 n = i + (n - i) 로 나타낼 수 있고, (n - i)의 값과 i의 값이 소수인지를 확인하면 된다.

또, 반만 확인해주면 된다.

 

정답 코드

num = int(input())

prime_tabel = [1 for i in range(1000001)]
prime_tabel[1] = 0

for i in range(2, 500001):
    if prime_tabel[i] ==1:
        j = 2
        while i*j <= 1000000:
            prime_tabel[i*j] = 0
            j += 1

while(num):
    num -= 1
    n = int(input())
    count = 0
    for i in range(2, n // 2 + 1):
        if(prime_tabel[i]==1):
            if(prime_tabel[n - i] == 1):
                count += 1
    print(count)

 

코드 설명

prime_tabel = [1 for i in range(1000001)]
prime_tabel[1] = 0

prime_table이 소수인지 아닌지를 확인하는 list이다. 0부터 100000까지 1로 초기화 시킨다.

1은 소수가 아니기 때문에, prime_table[1] = 0으로 해준다.

 

에라토스테네스의 체

for i in range(2, 500001):
    if prime_tabel[i] ==1:
        j = 2
        while i*j <= 1000000:
            prime_tabel[i*j] = 0
            j += 1

반만 해준다, 곱하는 값이 주어진 max 크기보다 작을 동안, 해당 배수의 자리를 1에서 0의 값으로 바꿔준다.

 

while(num):
    num -= 1
    n = int(input())
    count = 0
    for i in range(2, n // 2 + 1):
        if(prime_tabel[i]==1):
            if(prime_tabel[n - i] == 1):
                count += 1
    print(count)

num 번 반복.

2부터 n의 반절까지 진행시키고, 만약에 i의 값과 n-i의 값이 1, 즉, prime일 경우에 count(골드바흐의 파티션 수)에 1을 더해준다.

ex) 만약에 n = 6일 경우, 골드바흐의 파티션 수는 1일텐데,

3+3일 것이다.

i = 2, n - i = 4 => 둘다 1이 아님

i = 3, n - i = 3 => 둘다 1임, 골드바흐의 파티션 수를 저장하는 변수인 count 에 1을 더함

이런 느낌이다 ㅎㅎ