[알고리즘] 소수 찾기 - 에라토스테네스의 체 by javascript

소수를 찾는 수많은 방법중에서 가장 많이 사용된다는 "에라토스테네스의 체" 라는 소수 찾기 알고리즘에 대해 알아보자.

 

우선 소수란 무엇일까?

소수란 간단하게 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의할 수 있다.

 

그럼 에라토스테네스의 체란 무엇일까?

고대 그리스 수학자 에라토스테네스가 발견했다는 소수를 찾는 방법인데, 그림과 설명을 통해 자세히 접해보자.

---

알고리즘

1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (그림에서 회색 사격형으로 두른 수들이 해당한다.)

2) 2는 소수이므로 오른쪽에 2를 쓴다.

3) 자기 자신을 제외한 2의 배수를 모두 지운다.

4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 쓴다.

5) 자기 자신을 제외한 3의 배수를 모두 지운다.

6) 남아있는 수 가운데 5는 소수이므로 오른쪽에 쓴다.

7) 자기 자신을 제외한 5의 배수를 모두 지운다.

8) 남아있는 수 가운데 7은 소수이므로 오른쪽에 쓴다.

9) 자기 자신을 제외한 7의 배수를 모두 지운다.

10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

그림의 경우, 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

---

이제 개념을 어느정도 잡았다면 이에 대한 javascript언어로 코드를 구현해 보자.

 

javascript 에라토스테네스의 체 구현

function solution(n){
    let arr = Array(n + 1).fill(true).fill(false, 0, 2);
    for(let i = 2 ; i * i <= n; i++){
        if(arr[i]){
            for(let j = i * i; j <= n; j+=i){
                arr[j] = false;
            }
        }
    }

    return arr;
}

let isPrimes = solution(100);

// 소수의 개수 구하기
isPrimes.filter(e => e).length; // 25

// 소수 반환하기
isPrimes.map((v, i) => (v) ? i : 0).filter(e => e);
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

 

코드에 대해 하나씩 알아보자.

 

우선 주어진 숫자로부터 1. 기준 배열을 만들어야하는데, 주어준 숫자를 포함하는 배열이여야 하기 때문에 Array(n + 1)를 통해 배열을 생성해주었으며, 그 다음 fill() 메서드를 사용하여 전부 true로 바꿔준 뒤 0 과 1은 소수에서 제외시키기 때문에 미리 false로 바꿔준 것이다.

 

그래서 반복문의 시작을 보면 2부터 시작하는것을 볼 수 있다.

 

이제 여기서 2. i * i 가 뭐냐면 이건 위 알고리즘 설명에서 11^2가 120보다 큰 경우는 의미가 없다고 설명한 바 있다.

그렇게 때문에 선언해준 부분이다 의미없는 반복은 돌릴 필요 없으니까.

 

그리고 그 다음 안에서 3. 이중 반복문을 실행하는데, 위 알고리즘 설명처럼 배수를 전부 제거해주는 반복문이다.

 

이정도만으로도 이제 에라토스테네스의 체를 구현한 것이며,

결과값으로 true, false로 이루어진 배열을 반환할텐데 이걸 가지고 개수나 실제 소수의 배열로 만들어 사용이 가능하다.

---

 

추가적으로 소수를 판별하고자 한다고 하면 다른 게시글도 같이 참고하면 좋다.

https://mine-it-record.tistory.com/509

[알고리즘] 소수 판별하기 - 여러가지 방법의 소수 판별법 by javascript

---

참고 및 출처 : 위키백과 - 에라토스테네스의_체

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