요즘 백준 단계별로 문제풀기 문제를 풀고 있다.
지금 풀고 있는 단계는 약수, 배수, 소수를 다루는 단계를 풀고 있는데 소수를 활용한 문제를 풀다보니 에라토스테네스의 체를 사용하는 문제를 많이 볼 수 있었다.
간단하게 소수를 구하는 문제를 풀 때는 소수 판별 함수를 작성해서 풀고는 했는데 이를 사용하면 주어진 숫자의 범위가 너무 클 경우 시간초과가 발생한다.
그럴 때 활용하기 좋은 방법이 에라토스테네스의 체!
📌 에라토스테네스의 체란?
임의의 자연수 N에 대해 그 이하의 소수를 찾는 방법.
체로 쳐내듯이 수를 걸러내는 방법이라고 불리는 이름!
💡 알고리즘 구현
- 2부터 소수를 구하고자 하는 모든 구간의 수를 나열한다.
- 2부터 시작해 나열된 수에서 가장 작은 소수 2를 선택하고 2의 배수를 지운다.
- 다음으로 3을 선택해 3의 배수들을 지운다.
- 4는 2의 배수로 지워졌기 때문에 넘어가고 그 다음 수인 5를 선택해 5의 배수를 지운다.
- 위와 같은 과정 반복
- 반복이 끝난 후 지원지지 않고 남은 수들은 곧 소수.
하지만!
에라토스테네스의 체는 모든 범위의 수가 소수인지 아닌지를 리스트 형태로 저장해서 보는 경우가 많은데 그렇기 때문에 메모리를 많이 차지한다는 단점이 있다.
그래도 시간적인 면에서는 소수 판정 함수보다는 더 효율적이다!
👩🏻💻 [백준 17103] 골드바흐 파티션
문제 설명
짝수 N이 주어질 때 이 N을 두 소수의 합으로 표현할 수 있는 경우의 수 출력.
두 수의 순서가 다른 것은 같은 파티션으로 취급한다.
📌 문제 해결 방법
- 짝수 N이 주어지면 N을 만들 수 있는 순서쌍을 찾는다.
- 이 순서쌍을 이루는 두 수가 모두 소수인지를 검사한다.
- 두 수가 모두 소수인 쌍의 개수를 구한다.
첫 번째 풀이 방법 - 시간초과 발생 !
단순 소수 판별 함수 작성해서 모든 경우의 두 수를 소수인지 판별하도록 함
import sys
# 시간초과 발생
def is_prime(N):
if N == 1:
return False
# 시간초과 방지를 위해 제곱근까지만
for i in range(2, int(N**0.5) + 1):
if N % i == 0:
return False
return True
T = int(sys.stdin.readline())
for _ in range(T):
N = int(sys.stdin.readline())
cnt = 0
# 다른 순서 중복 방지
for i in range(2, N // 2 + 1):
if is_prime[i] and is_prime[N - i]:
# 두 수가 전부 다 소수여야 함
cnt += 1
print(cnt)두 번째 풀이 방법 - 에라토스테네스의 체 활용
위의 방법을 쓰니 시간초과가 발생해서 소수 판별 함수 작성 부분만 에라토스테네스의 체로 변경하였다!
import sys
# 해결 : 에라토스테네스의 체 이용
is_prime = [True] * 1000001 # 인덱스가 곧 숫자
is_prime[0] = is_prime[1] = False # 0,1은 소수가 아님
for i in range(1000001):
if is_prime[i]:
for k in range(2 * i, 1000001, i):
is_prime[k] = False
T = int(sys.stdin.readline())
for _ in range(T):
N = int(sys.stdin.readline())
cnt = 0
# 다른 순서 중복 방지
for i in range(2, N // 2 + 1):
if is_prime[i] and is_prime[N - i]:
# 두 수가 전부 다 소수여야 함
cnt += 1
print(cnt)시간초과는 발생하지 않았지만 메모리를 더 많이 차지하기 때문에 그래도 꽤 오랜 시간이 걸렸다.
메모리 제한이 크게 걸려있지 않은 소수 관련 문제는 앞으로는 에라토스테네스의 체를 활용해서 푸는 게 시간복잡도 면에서 훨씬 좋을 거 같다! 이번을 기회로 절대절대 까먹지 않기를💡
