[구현] (2-7) 소수찾는 가장 작은 시간복잡도 : 에라토스테네스의 체

문제: 소수(에라토스테네스 체)

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.

<입력설명>
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

<출력설명>
첫 줄에 소수의 개수를 출력합니다.

• 입력예제 20
• 출력예제 8

블로그 앞의 글들에서 N의 약수를 찾을때에, 내가 고안한 방법의 시간복잡도는 O(sqrt(N))이었다.

그리고 그동안 소수를 구할때 약수를 구하는 방법에서 조금 변형해서 코드를 작성해왔다.

import sys
input = sys.stdin.readline
from math import sqrt

N = int(input())

median = sqrt(N)

cnt_not_era = 0
for i in range(2, N+1):
    if i == 2:
        continue
    median = int(sqrt(i))
    cnt_yak = 0
    for j in range(2, median+1):
        if i%j == 0:
            cnt_not_era += 1
            break
print(N-cnt_not_era-1)

 

N의 소수를 구하기 위해서, 2부터 N까지 쭉 for문을 도는데,

 for문안의 수 (i)가  2~sqrt(N) 까지 약수가 존재한다면 배제하는 것이다.

https://leerosepark.tistory.com/25 를 보면 약수를 구하는 코드를 알 수 있다.

 

그렇다면 이러한 코드의 시간복잡도는 어떻게 될까?

 

• 외부 루프 (for i in range(2, N+1)):
  • 이 루프는 N-1번 반복됩니다.
• 내부 루프 (for j in range(2, median+1)):
  • 각 i에 대해 내부 루프는 최대 sqrt(i)번 반복됩니다.
  • 최악의 경우 i는 N이 될 수 있으므로 내부 루프는 최대 sqrt(N)번 반복됩니다
• 최종적으로 Nsqrt(N), 즉 N^(3/2)의 시간복잡도를 가진다.

 

 

그러나 위 문제처럼 N이 200,000일때는, 200,000 * sqrt(200,000) ~= 200,000 * sqrt(20) * 100 ~= 20,000,000 * 5 = 100,000,000가 된다.

 

보통 2초의 시간제한이 있다면,  어림잡아 시간복잡도가 2억이라 가정하기때문에, 위 구현으로 가능하나, 역시나 위험부담이 있다.

 

그런 고민과 함께 문제 제목인 '아레스토테네스 체'를 구글에 검색해보았는데 깜짝놀랐다.

N ( ln ( ln N ) ) 의 시간복잡도로 소수를 찾는 코드를 구현 할 수 있었다.

 

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체

 

2~N까지의 순서로 탐색을하는데, 현 탐색하는 숫자의 배수들을 제거해 나가는 방법이다.

처음인 2의 차례에선 2를 제외한 모든 짝수들이 제거될것이고,

3의 차례에서는 3의배수들(6의 배수는 이미 2에서 제거됨)이 제거 될 것이다.

그렇게 되면 4는 제거되었으므로 자연스럽게 건너뛰게 되고,

그다음 차례인 5는 반드시 소수일 것이며 (5보다 작은 소수들의 배수가 아니므로) 5의 배수들을 제거한다.

 

2~N까지 순차적으로 for문을 돌리면서 배수를 제거하는 작업을 한다면,

다음 i의 배수를 제거하게 될때, 그 i는 반드시 소수일 것이다.

 

import sys
input = sys.stdin.readline

N = int(input())
num_list = [0] * (N+1)
cnt = 0
for idx in range(2, N+1):
    if num_list[idx] == 0:
        cnt+=1
        for i in range(idx, N+1 ,idx):
            num_list[i] += 1

print(cnt)

 

 

이러한 수학적인 이유로 시간복잡도가 다음과 같이 되니, 위 방법을 기억해두자.