[JS] 소수 판별

n까지 모두 판별

const isPrime = (n) => {
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

n의 제곱근 (√n) 까지

n의 제곱근 (√n) 값으로 나누어 떨어지면 √n의 배수라는 뜻이므로 소수가 아니게 된다.

const isPrime = (n) => {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

에라토스테네스의 체

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의 배수를 지우고 남는 수는 모두 소수이다.

구현

function eratos(n) {
    const 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 = eratos(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/507