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

에라토스테네스의 체란?

1. 수학에서 에라토스테네스의 체는 고대 그리스에서 에라토스테네스가 발견한 소수를 찾는 방법이다.

2. 소수를 찾는 알고리즘 중에 하나로 2부터 찾고자하는 숫자의 범위 n의 값이 크면 클수록 효과적이다.

3. 알고리즘은 아래 사진과 같다.

 

에라토스테네스의 체

 

알고리즘

1. 2부터 소수를 구하고자 하는 모든 수를 나열한다. 그림에서 회색 사각형으로 다른 수들이 여기에 해당한다.

2. 2는 소수이므로 오른쪽 Prime numbers에 2를 써준다.

3. 2를 제외한 모든 2의 배수를 지운다.

4. 3은 소수이므로 오른쪽 Prime numbers에 3을 써준다.

5. 3을 제외한 모든 3의 배수를 지운다.

6. 5는 소수이므로 오른쪽 Prime numbers에 5를 써준다.

7. 5를 제외한 모든 5의 배수를 지운다.

8. 7은 소수이므로 오른쪽 Prime numbers에 7을 써준다.

9. 7을 제외한 모든 7의 배수를 지운다.

10. 위 과정을 구하고자하는 i를 2부터 i*i가 n보다 작거나 같을때 까지만 수행해주면 된다.

 

[js] 예제코드

let primeNumber = [];
primeNumber[0] = false;
primeNumber[1] = false;

const n = 120;
for (let i = 2; i <= n; i++) primeNumber[i] = true;

for (let i = 2; i * i <= n; i++) {
  if (primeNumber[i]) {
    for (let j = i * i; j <= n; j += i) {
      primeNumber[j] = false;
    }
  }
}

for (let i = 1; i <= n; i++) if (primeNumber[i]) console.log(i);

결과값으로 위 사진과 같이 소수들이 출력되는 것을 확인할 수 있다.

 

outer 반복문에서 i*i까지만 확인하는 이유는 아래와 같다.

2023.06.15 - [개발 팁 정리] - [알고리즘] 에라토스테네스의 체에서 소수 판정 시 제곱근 까지만 확인하면 되는 이유

[알고리즘] 에라토스테네스의 체에서 소수 판정 시 제곱근 까지만 확인하면 되는 이유