[알고리즘] 소수 판별하기

소수란?

소수란 1과 자신만으로 나누어 떨어지는 1보다 큰 양의 정수를 뜻한다.

2, 3, 5, 7, 11, 13 ... 와 같은 수는 소수가 된다.

 

소수를 구하는 방법에 대해 알아보자.

n까지 모두 판별하기

1이 아닌 2부터 n사이의 모든 정수를 다 확인하는 방법

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

    return true;
}

n의 제곱근 (√n) 까지만 계산하기

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

 

예를 들어 25의 제곱근은 √25(5) 이다.

이때 5까지만 반복문이 돌아가더라도 25는 5의 배수이므로 i가 5일 때 나누어 떨어지게 되고 소수가 아님을 판별할 수 있게 된다.

 

다른 예시로 49의 제곱근은 √49(7)입니다. 49도 7의 배수이므로 i가 7일 때 나누어 떨어지므로 소수가 아님을 알 수 있다

 

즉 처음에 소개한 2, 3, 5, 7, 11, 13... 의 배수까지는 비교할 필요가 없습니다.

하지만 1은 소수가 아니기에 따로 구분을 해줘야합니다.

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

    return true;
}

에라토스테네스의 체

이 방법은 2부터 n까지의 자신을 제외한 배수를 제거하다 보면 소수만 남는다는 원리이다.

어떤 수의 배수가 되는 수는 (1과 자신의 수)가 아닌 다른 수로 나누어 떨어지기에 소수가 될 수 없다.

 

이때 위 예시처럼 √n까지만 판별을 해도 결과는 똑같다.

const isPrime = (n) => {                
  const prime = {};

  for (let i = 2; i <= Math.ceil(Math.sqrt(n)); i++) {
    if (prime[n]) {
      break;
    }

    if (prime[i]) {
      continue;
    }

    for (let j = i ** 2; j <= n; j += i) {      
        prime[j] = true;
    }
  }

  return !prime[n];
}