소수란 무엇인가?
소수(prime number)는 1보다 큰 자연수 중에서 두 개의 더 작은 자연수를 곱하여 만들 수 없는 수를 말합니다. 다시 말해, 1과 자기 자신만을 약수로 가지는 수입니다. 대표적인 예로 2, 3, 5, 7, 11 등이 있으며, 1보다 크면서 소수가 아닌 자연수는 모두 합성수(composite number)라고 부릅니다.
소수 판별(primality test)은 입력으로 주어진 숫자가 소수인지 아닌지를 판별하는 알고리즘을 의미합니다.
이번 글에서는 숫자 하나를 인자로 받아 해당 숫자가 소수인지 여부를 확인하는 JavaScript 함수를 작성해 보겠습니다.
구현 예제
다음은 주어진 숫자가 소수인지 검사하는 코드입니다 −
const findPrime = (num = 2) => {
if (num % 1 !== 0) {
return false;
}
if (num <= 1) {
return false;
}
if (num <= 3) {
return true;
}
if (num % 2 === 0) {
return false;
}
const dividerLimit = Math.sqrt(num);
for (let divider = 3; divider <= dividerLimit; divider += 2) {
if (num % divider === 0) {
return false;
}
}
return true;
};
console.log(findPrime(2));
console.log(findPrime(97));
console.log(findPrime(131));
console.log(findPrime(343));
코드 동작 원리
위 함수는 다음과 같은 단계로 동작합니다.
- 정수 검사: num을 1로 나눈 나머지가 0이 아니라면 정수가 아니므로 false를 반환합니다.
- 1 이하 처리: 소수는 1보다 커야 하므로 1 이하의 값은 false를 반환합니다.
- 2와 3 처리: 2와 3은 소수이므로 즉시 true를 반환합니다.
- 짝수 제거: 2를 제외한 모든 짝수는 소수가 될 수 없으므로 false를 반환합니다.
- 제곱근까지 검사: 어떤 수의 약수는 반드시 그 수의 제곱근 이하에 존재하므로, 3부터 √num까지 홀수만 검사하면 충분합니다. 이렇게 하면 모든 수를 일일이 나누어 보는 것보다 훨씬 효율적입니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다 −
true true true false
2, 97, 131은 소수이므로 true가 출력되고, 343은 7 × 49로 나눌 수 있는 합성수이므로 false가 출력됩니다.