소수

1과 자기 자신을 약수로 갖는 모든 자연수 ( 2, 3, 5, 7, 11 ... ) 를 말한다.

일반적인 소수 판별 방법

일반적으로 소수는 다음과 같이 판별할 수 있다.

function isPrime(x) {
  for (let i = 2; i < x; i++) {
    if (x % i === 0) return false;
    return true;
  }
}

console.log(isPrime(100));
console.log(isPrime(99));

2부터 자기 자신의 바로 직전 숫자 중 하나라도 약수가 발견되면 소수가 아니다.

하지만 이 방식은 2부터 자기 자신의 바로 직전까지 모든 경우의 수 를 다 돌면서 확인한다는 점에서 시간 복잡도가 O(N)으로, 비효율적 이다.

더 효율적인 방법

일반적으로 모든 수의 약수는 대칭을 이룬다. 예를 들어 10은 2 x 5 = 5 x 2 로 약수가 대칭을 이룬다.

여기서 숫자의 제곱근 까지만 약수 여부를 검증해도 소수를 판별할 수 있다 는 점을 알 수 있다.

function isPrime(x) {
  let end = Math.sqrt(x);
  for (let i = 2; i < end; i++) {
    if (x % i === 0) return false;
    return true;
  }
}

console.log(isPrime(100));
console.log(isPrime(99));

특정 숫자의 제곱근까지만 검사해도, 약수의 대칭성 덕분에 소수 판별이 가능하다.

에라토스테네스의 체

대량의 소수를 한꺼번에 판별할 때는 더 효율적인 방법이 필요하다. 이 때 사용하는 것이 바로 에라토스테네스의 체 이다.

100 이하의 소수를 찾아보자.

1. 1부터 자기 자신까지 숫자를 쭉 쓴다.
2. 2를 제외한 2의 배수를 지운다.
3. 3을 제외한 3의 배수를 지운다.
4. 4의 배수를 지울 차례지만 이미 2번에서 지워졌으므로 건너뛴다.

쭉쭉 지운다.

5. 남은 숫자들을 출력한다.

[ 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 ]

이렇게해서 소수를 구했다.

위키백과에서 제공하는 그림 설명이다.

에라토스테네스의 체는 임의의 자연수 N 이하의 소수를 찾는 방법 중 가장 간단하고 빠른 방법이다.

JavaScript로 구현

에라토스테네스의 체를 JavaScript로 구현해보자.

function eratosthenesSieve(array, number) {
  let tempArray = [];

 for (let i = 2; i <= number; i++) {
    tempArray[i] = i;
 }

 for (let i = 2; i <= number; i++) {
   if (tempArray[i] === 0) continue;

   for (let j = i + i; j <= number; j += i) {
     tempArray[j] = 0;
   }
 }

 for (let i = 2; i <= number; i++) {
   if (tempArray[i] !== 0) {
     array.push(tempArray[i]);
   }
 }

  return array;
}

let result = [];
console.log(eratosthenesSieve(result, 100));

1. 먼저 빈 배열 tempArray를 선언 후, 2부터 자기 자신까지 넣는다.
   [ 2, 3, 4, 5, 6, ... 98, 99, 100 ] 이 될 것이다.
2. 2와 3은 이미 소수이므로, 2의 배수인 4부터 검사를 시작한다.
3. 4부터 자기 자신까지 2를 더해가면서, 해당되는 숫자를 모두 0으로 바꾼다.
4. 6부터 자기 자신까지 3을 더해가면서, 해당되는 숫자를 모두 0으로 바꾼다.
   소수가 아니기 때문이다.
5. 이렇게 자기 자신까지 모두 검사해서 소수가 아닌 숫자는 모두 0으로 바꾼다.
6. 검사가 끝나면
   [ 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 ]
   이처럼 소수만이 남게 된다.