수학에서 메르센 소수(Mersenne prime)는 어떤 정수 n에 대해 M(n) = 2n − 1의 형태로 나타낼 수 있으면서 실제로 소수인 수를 의미합니다.
예를 들어, 가장 작은 네 개의 메르센 소수는 3, 7, 31, 127입니다. 각각 2²−1, 2³−1, 2⁵−1, 2⁷−1로 표현할 수 있기 때문입니다.
이번 글에서는 하나의 숫자를 입력받아 해당 숫자가 메르센 소수인지 판별하는 자바스크립트 함수를 작성해 보겠습니다.
메르센 소수의 판별 조건
어떤 수가 메르센 소수이려면 다음 두 가지 조건을 모두 만족해야 합니다.
- 그 수 자체가 소수여야 합니다.
- 그 수에 1을 더한 값이 2의 거듭제곱(2ⁿ)이어야 합니다. 즉, num + 1 = 2ⁿ을 만족해야 합니다.
구현 예제
const isPrime = num => {
let i = 2;
while(i <= num / 2){
if(num % i++ === 0){
return false;
};
};
return true;
}
const mersennePrime = num => {
if(!isPrime(num)){
return false;
};
let i = 0, n = num+1;
while(n !== 1){
if(n % 2 !== 0){
return false;
};
n /= 2;
};
return true;
};
console.log(mersennePrime(31));
console.log(mersennePrime(127));
console.log(mersennePrime(3));
console.log(mersennePrime(37));
console.log(mersennePrime(87));
console.log(mersennePrime(7));코드 설명
isPrime 함수는 2부터 num/2까지의 수로 차례대로 나누어 보며 약수가 존재하면 false를 반환하고, 끝까지 나누어 떨어지지 않으면 true를 반환하는 기본적인 소수 판별 함수입니다.
mersennePrime 함수는 먼저 입력받은 수가 소수인지 확인합니다. 소수가 아니라면 즉시 false를 반환합니다. 이후 num + 1 값을 2로 계속 나누면서, 나누는 도중 홀수가 등장하면 false를 반환하고 최종적으로 1에 도달하면 true를 반환합니다. 이 과정을 통해 num + 1이 2의 거듭제곱인지 검증할 수 있습니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true true true false false true
31, 127, 3, 7은 메르센 소수이므로 true가 출력되고, 37은 소수이지만 37 + 1 = 38이 2의 거듭제곱이 아니며, 87은 3 × 29로 소수가 아니므로 false가 출력됩니다.
참고: 더 효율적인 검사 방법
비트 연산을 활용하면 2의 거듭제곱 여부를 더 간단하게 확인할 수 있습니다. num + 1이 2의 거듭제곱일 때 (num & (num + 1)) === 0이 항상 성립하므로, 반복문 없이 한 번의 비트 AND 연산으로 조건을 검사할 수 있습니다.