소수 구하기 - 에라토스테네스의 체 (Python & JavaScript)

우리는 알고리즘 공부를 하다보면 소수에 대한 문제를 가끔 보게 된다. 그러나 이는 구현하는 방식에 따라 시간 복잡도가 달라지는데 우리는 이번 시간에 에라토스테네스의 체를 이용해서 소수를 탐색할 수 있다.

이 방식의 시간 복잡도는 선형 시간과 비슷한 시간으로 O(NloglogN)이다.

---

에라토스테네스의 체 알고리즘

이는 다수의 자연수에 대해서 소수 여부를 판별할 때 사용되는 대표적 알고리즘이다. 동작 방법은 가장 작은 소수(i)를 찾고 이에 배수가 되는 값들을 제외한다. 제외한 뒤에는 소수 다음 중 가장 작은 소수를 찾아 배수가 되는 값을 제거하는 방법을 반복하면 된다.

 

동작과정

• 2부터 N까지의 모든 자연수를 담고 있는 하나의 배열에 생성한다.
• 배열에서 남은 수 중에서(True인 수) 아직 처리하지 않은 가장 작은 수 i를 찾는다.
• 남은 수 중에서 i의 배수를 모두 제거한다.
• 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

📌 이때 범위은 2 ~ n의 제곱근 범위 내에서만 i를 확인하면 된다.

 

Python

def primeList(n):
    arr = [True for i in range(i + 1)]

    for i in range(2, int(n ** 0.5 + 1)):
        if arr[i] == True:
            for j in range(i + i, n, i):
            	arr[j] = False
    return [i for i in range(2, n) if arr[i] == True]

 

JavaScript

const primeList = (n) => {
      let arr = Array.from({length : n}, () => true)
      for (let i = 2; i <= Math.sqrt(n) + 1; i += 1) {
          if (arr[i] === true)
              for (let j = i * i; j <= n; j += i)
                  arr[j] = false;
      }
      answer = []
      for (let i = 2; i <= n; i += 1) {
          if (arr[i] === true) answer.push(i)
      }
      return answer
}