[JS] 소수 판별하기

소수란?

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

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

 

소수를 구하는 3가지의 방법을 알아보겠습니다.

 

 

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까지만 판별을 해도 결과는 똑같습니다.

 

√25(5)는 5의 배수인 10, 15, 20, 25는 배수로 쳐 소수가 아닌 수로 분류됩니다.

그리고 5의 다음인 6은 이미 2의 배수로 소수가 아님이 분류가 완료되었기에 판별할 필요가 없어집니다.

 

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];
}

현재의 수(i)에서 n까지의 배수를 모두 담아주고 마지막에 구할려는 수가 들어있는지를 판별해준 코드입니다.