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

개요

가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 임의의 자연수 n에 대해 그 이하의 소수를 찾는 방법 중 가장 간단하고 빠른 알고리즘으로 알려져 있다.

---

방법

1. 1~n까지 숫자를 배열에 쓴다.

   1	2	3	4	5
   6	7	8	9	10
   11	12	13	14	15
   16	17	18	19	20
   21	22	23	24	25

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

   1	2	3		5
   	7		9
   11		13		15
   	17		19
   21		23		25

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

   1	2	3		5
   	7
   11		13
   	17		19
   		23		25

   이미 지워져 있을 경우 건너뛴다.

4. 반복한다.

   1	2	3		5
   	7
   11		13
   	17		19
   		23

5. 2부터 시작하여 남아있는 숫자들이 소수이다.
   2, 3, 5, 7, 11, 13, 17, 19, 23

---

소스 코드

const num = 100;
const a = new Array(num + 1);

for (let i = 2; i <= num; i++) {
  a[i] = i;
}
a[1] = 0;

for (let i = 2; i <= num; i++) {
  if (a[i] === 0) continue;
  for (let j = i + i; j <= num; j += i) {
    a[j] = 0;
  }
}

a.filter(n => n !== 0).forEach(n => console.log(n));

---

참고 블로그

https://blog.naver.com/ndb796/221233595886