C++로 구현하는 메르센 소수(Mersenne Prime) 찾기

메르센 소수란?

수학에서 메르센 소수(Mersenne prime)는 2의 거듭제곱에서 1을 뺀 값이 소수인 수를 의미합니다. 즉, 어떤 정수 n에 대해 M_n = 2ⁿ − 1 형태를 만족하는 소수입니다.

메르센 소수가 되는 지수 n은 2, 3, 5, 7, ... 순으로 나타나며, 이에 대응하는 메르센 소수는 각각 3, 7, 31, 127 입니다.

이번 글에서는 입력으로 주어진 양의 정수 n보다 작거나 같은 모든 메르센 소수를 출력하는 C++ 프로그램을 작성해 보겠습니다.

알고리즘 접근 방식

문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.

1. 에라토스테네스의 체를 이용해 주어진 수 n 이하의 모든 소수를 미리 구한다.
2. 2^i − 1 형태의 수를 차례대로 순회하면서, 해당 값이 소수인지 확인하고 소수라면 출력한다.

여기서 비트 시프트 연산자 <<를 활용하면 2ⁱ − 1 값을 곱셈 없이 빠르게 계산할 수 있다는 장점이 있습니다.

C++ 예제 코드

#include <iostream>
#include <algorithm>
using namespace std;

// 에라토스테네스의 체로 n 이하의 소수를 구하는 함수
void generatePrimes(bool *primes, int n){
    fill(primes, primes + n + 1, true);
    for (int p = 2; p * p <= n; ++p) {
        if (primes[p] == true) {
            for (int i = p * 2; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }
}

// n 이하의 메르센 소수를 출력하는 함수
void mersennePrimes(int n){
    bool primes[n + 1];
    generatePrimes(primes, n);
    for (int i = 2; ((1 << i) - 1) <= n; ++i) {
        int num = (1 << i) - 1;
        if (primes[num]) {
            cout << num << " ";
        }
    }
    cout << endl;
}

int main(){
    int n = 100;
    cout << "Mersenne primes numbers till " << n << endl;
    mersennePrimes(n);
    return 0;
}

코드 동작 원리

generatePrimes 함수는 고전적인 에라토스테네스의 체 방식으로 동작합니다. 먼저 모든 인덱스를 true로 초기화한 뒤, 2부터 시작해 각 소수의 배수들을 false로 표시하여 n 이하의 소수만 남깁니다.

mersennePrimes 함수는 위에서 만든 소수 테이블을 활용합니다. (1 << i) - 1 연산으로 2ⁱ − 1 값을 구하고, 그 값이 n 이하인 동안 반복하면서 소수 테이블에 존재하는 경우에만 화면에 출력합니다.

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Mersenne primes numbers till 100
3 7 31

100 이하의 메르센 소수는 3, 7, 31 세 개뿐임을 확인할 수 있습니다. 참고로 다음 지수인 13에 해당하는 8191(= 2¹³ − 1)도 메르센 소수이지만, 100보다 크기 때문에 이 범위에서는 나타나지 않습니다.