에라토스테네스의 체

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

 

0. 소수

소수란 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말한다.

 

1. 에라토스테네스의 체 란?

소수를 판별하는 알고리즘이다.

소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

그 중 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우에 가장 좋은 효율을 보인다.
(이때 시간 복잡도는 O(Nlog (logN))이다. 하지만 필요없는 숫자들의 소수도 판별해야 하기에 숫자가 커지면 커질수록 비효율적이다.

또한, 에라토스테네스의 체 과정상 주어진 정수범위 N의 크기만큼 리스트나 배열등을 할당해야하기 때문에 메모리가 많이 필요하다는 것도 단점이다.)

 

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이며 이 방법은 마치 체로 치듯이 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방법이며, 프로그래밍에서는 상당히 효율적인 방법론이 된다.

에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧다.

 

2. 에라토스테네스의 체 과정

<주어진 범위 정수N이 120일 경우 예제>

1. 2 ~ 주어진 범위 N까지의 모든 숫자를 나열한다.

2. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들을 모두 지운다. (빨간색)

3. 남아있는 숫자에서 3은 소수이므로 오른쪽에 3을 쓰고 3의 배수들을 모두 지웁니다. (초록색)

4. 남아있는 숫자에서 5는 소수이므로 오른쪽에 5를 쓰고 5의 배수들을 모두 지웁니다. (노란색)

5. 위의 과정을 반복합니다.

6. 예제에서는 11X11은 121로 범위 2 ~ 120을 넘기 때문에 반복을 멈추고 남은 수(소수)들을 출력합니다.

 

3. 예제 문제

프로그래머스 2024.01.16 (1Lv 소수 찾기)

해당 문제는 단순 소수의 개수만 알아내면 되기 때문에 따로 소수들을 빼지 않아도 된다.

 

4. 참고 블로그 및 자료

[Algorithm] 에라토스테네스의 체 - 소수 구하기 (범위)

 

[Algorithm] 에라토스테네스의 체

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전