에라토스테네스의 체(프로그래머스 - 소수 찾기)
배경
알고리즘 문제풀이 플랫폼인 “프로그래머스” 하루에 최소 한 문제씩 풀어보고 있다. 레벨 0문제를 다 풀고 레벨 1문제를 정답율 높은 문제부터 하나씩 풀어가고 있던 중, “소수 찾기” 문제를 만났다.
문제를 보는 순간 42서울의 라 피신(la piscine) 기간에 학습했던 “에라토스테네스의 체”를 떠올렸고, 기억나는대로 구현했다. 이 때 나는 몇 가지 내용을 애매하게 알고 있었다.
- 에라토스테네스의 이름이 에라토스테네스인지, 에라스토테네스인지
- 반복문을 수행하는 범위를 주어진 수 N까지로 할 것인지 N의 제곱근까지 할 것인지
첫 번째 애매한 점은 검색 한 번으로 해결할 수 있었다. 두 번째 애매한 것도 검색하면 되긴 했지만, 우선 반복문의 범위를 N으로 잡기로 했다. 제곱근까지만 하면 되는 걸로 알고 있었지만, 증명이 기억나지 않았기 때문이다. 일단 구현하고, 다시 공부하기로 마음먹었다.
구현
그래서 구현한 첫 번째 버전은 아래의 코드다.
def solution(n):
result = [1] * (n + 1)
result[0:2] = [0, 0]
for idx in range(2, n):
mul = 2
current = idx * mul
while current <= n:
if result[current] == 1:
result[current] = 0
mul = mul + 1
current = idx * mul
return sum(result)
레벨 1에서 나온 문제여서인지 이렇게 풀어도 정답으로 처리됐다.
개선
풀이를 마친 후 N의 제곱근까지만 수행하면 되는 이유를 알기 위해 Cursor 에디터에서 위 코드를 효율적인 알고리즘으로 개선해달라고 요청했고, 아래와 같은 코드를 제안받았다.
def solution(n):
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for start in range(2, int(n**0.5) + 1):
if sieve[start]:
for i in range(start * start, n + 1, start):
sieve[i] = False
return sum(sieve)
에라토스테네스의 체에서 반복문의 범위
역시 int(n**0.5) + 1으로 제곱근보다 작은 수까지만 반복문을 수행하는 코드를 작성해줬다. Cursor의 설명을 통해 왜 제곱근까지만 수행하면 되는지 알 수 있었다.
만약 X가 소수가 아니라면, 특정 수 M에 N을 곱해야 X를 만들 수 있다. X = M * N이라고 할 때, M이 제곱근보다 큰 수라면, N은 제곱근보다 반드시 작아야 한다. 둘 다 제곱근보다 크다면 X < M * N이 되기 때문이다. 그런데, M이 제곱근보다 큰 수라면 이미 이전에 수행한 반복문에서 해당 값은 False로 판별이 된다. 예를 들어, X = 16, M = 8, N = 2라면 2에 대한 반복문을 수행할 때, 이미 16은 소수가 아닌 것으로 판별된 후인 것이다. 따라서 제곱근까지만 확인하면 그보다 큰 수는 더이상 확인할 필요가 없다.
사소한 수정
나는 sum()을 수행할 때, 숫자를 파악하기 위해 0, 1로 배열을 초기화 했다. 하지만 sum()은 리스트에서 True인 아이템을 셀 수 있었다.
>>> sum([True, True, False])
2
그리고 range() 함수의 세 번째 인자인 step을 통해 아래처럼 반복문을 작성할 수 있었다.
for i in range(start * start, n + 1, start):
sieve[i] = False
결과
결과적으로 Cursor의 코드 제안을 통해 아래와 같은 향상이 있었다. 아래는 Cursor에서 개선한 부분에 대해 설명해준 내용이다.
시간 복잡도: 기존 알고리즘은 O(n^2)에 가까운 복잡도를 가질 수 있었으나, 변경된 알고리즘은 O(n log log n)의 복잡도를 가집니다. 이는 특히 큰 n에 대해 매우 효율적입니다.
불필요한 계산 감소: start의 제곱부터 시작하여 배수를 제거함으로써, 이미 처리된 수에 대한 중복 계산을 피할 수 있습니다.
소수와 관련한 문제를 만나면 그때마다 에라토스테네스의 체를 구현하는데, 항상 애매한 기억을 토대로 구현하는 것 같아서 생각난 김에 – Cursor도 사용해볼 겸 – 포스트를 작성했다.