백준 문제 풀이를 하다가 새로운 개념이 있어서 문제 풀이와 함께 정리해보려고 한다.

문제 정보

문제

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

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

입력 예시와 출력 예시

입력

5
6
8
10
12
100

출력

1
1
2
1
6

문제 분석

먼저 골드바흐의 추측에 대한 설명은 친절하게 되어있다.
< 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. >
소수의 합이다. 소수는 1과 나 자신만을 약수로 가지는 것을 의미한다. 이걸 구하는 방법은 굉장히 다양하다. 그만큼 시간복잡도가 큰 것도 존재한다. 시간제한이 0.5초인 것을 볼 수 있는데 이를 도와주는 소수 구하는 법이 알고리즘 분류에 기록되어있다.

에라토스테네스의 체

에라토스테네스의 체란 무엇일까? 소수를 대량으로 구하는 것을 의미한다. 단순히 소수를 구하는 식을 구하면 아래 코드와 같다.

def is_prime(n):
	for i in range(2,n+1):
   	if n%i==0:
       	return False
   return True

여기서는 n에 값에 대해 2부터 n까지 구해야해서 많은 시간이 걸린다. 하지만 이렇게 처음부터 끝까지 구할 필요가 없다. n의 제곱근까지만 구하면 된다.

def is_prime(n):
	for i in range(2, int(n**(1/2))+1):
    	if n%i == 0:
        	return False
    return True

이렇게 n의 제곱근까지만 구해도 충분히 소수 판별이 가능하다.

에라토스테네스의 체와 각 소수 구하기

문제로 잠깐 돌아와보면 각 숫자에 대해 소수인지를 에라토스테네스의 체를 이용해서 구해줘야 한다. 그럼 최소한 구하고자 하는 숫자까지 위에 언급한 함수를 호출해야 할 것이다. 코드로 보자

def is_prime(n):
	for i in range(2, int(n**(1/2))+1):
    	if n%i == 0:
        	return False
    return True
n = 6
for i in range(2, n+1):
	is_prime(i)

방금 예시는 2부터 n까지 각 숫자가 소수인지 판단해주는 것이다. 여기까지만 보면 각 소수를 구하는 것은 어렵지 않아 보인다.

시간 복잡도의 제한

위 함수를 문제에 그대로 적용하면 시간초과가 뜬다. 0.5초라는 제한이 있는데 그러면 5000만 번의 제한이다. 각 경우의 수를 탐색하면서 해당 숫자까지 보기 때문에 1000000 * 1000 이렇게만 해도 1억번이 넘어간다. 에라토스테네스의 체의 함수를 조금 변형을 시켜야 한다.

코드 분석

에라토스테네스의 체 개선 방식

def make_primes(n):
    primes = [True] * (n+1)
    primes[0] = False #소수가 아님
    primes[1] = False #소수가 아님
    for i in range(2, int(n**(1/2))+1):
        if primes[i]:
            for j in range(i*i, n+1, i): #i의 제곱부터 n까지의 i배수 제거(소수가 아님)
                primes[j] = False
    return primes
    

위 함수는 한번 호출해서 문제에서 언급한 전체 범위에 대해 소수를 구하는 것이다. n의 제곱근까지만 탐색하면서도 여기서 다시 i의 제곱값부터 끝까지 i배수는 모두 소수가 아니라고 설정을 해줌으로서 소수 여부를 처리한다.

소수 여부 확인

for _ in range(t):
    n = int(input())
    cnt = 0
    
    for p in range(n//2 + 1): #n의 절반까지만 탐색하면 됨
        if primes[p] and primes[n-p]: #소수인지 확인을 하고 다른 값 하나도 확인해주면
            cnt += 1 #개수를 올린다.
    print(cnt) # 각 값을 출력

조금 전에 이미 소수 여부 상태가 담긴 배열을 만들어놓았기 때문에 각 경우마다 소수인지만 판단을 해주면 된다. n의 절반까지 탐색을 해준다. 이유는 '두 소수의 순서만 다른 것은 같은 파티션이다.'라고 언급했기 때문이다. 그래서 n의 절반까지만 탐색하면서 해당 숫자와 남은 값 n-p 값도 소수인지 체크해서 개수를 올려준다.

최종 코드

import sys

input = sys.stdin.readline
def make_primes(n):
    primes = [True] * (n+1)
    primes[0] = False #소수가 아님
    primes[1] = False #소수가 아님
    for i in range(2, int(n**(1/2))+1):
        if primes[i]:
            for j in range(i*i, n+1, i): #i의 제곱부터 n까지의 i배수 제거(소수가 아님)
                primes[j] = False
    return primes

primes = make_primes(1000000) #최대 범위까지 만들어놓음

t = int(input())

for _ in range(t):
    n = int(input())
    cnt = 0
    
    for p in range(n//2 + 1): #n의 절반까지만 탐색하면 됨
        if primes[p] and primes[n-p]: #소수인지 확인을 하고 다른 값 하나도 확인해주면
            cnt += 1 #개수를 올린다.
    print(cnt) # 각 값을 출력
    

코드를 합치면 다음과 같이 나오게 된다.

구현 후기

처음에는 짝수 n을 받아 구하는 방식을 취했지만 이는 시간복잡도가 굉장히 커지게 되었다. 그래서 한번에 최대 범위를 만들고 찾아내는 방식이 정답이었다. 개념적으로도 이해가 필요해서 찾아보고 구현했지만 배열로 저장해줘야 했기에 이 과정을 이해하는데에 시간이 조금 걸린 것 같다. 오랜만에 소수 구하기 관련 문제를 푼 것 같은데 이번에는 알고리즘 분류보고 코드를 가져오는 방식이었지만 안보고 할 수 있도록 해야 겠다.