[C/C++] 프로젝트 오일러 #97 Large Non-Mersenne Prime(수학)

메르센 소수(Mersenne Prime)는 아주 특별한 형태의 소수입니다. 소수란 1과 자기 자신 외에 다른 약수가 없는 숫자를 말하는데, 메르센 소수는 그 중에서도 다음과 같은 형태를 가진 숫자들입니다:

\[ M_p = 2^p - 1 \]

여기서 \(p\) 는 소수(Prime number)여야 합니다. 간단히 말해, 2의 거듭제곱에서 1을 뺀 숫자들 중에서 소수인 것을 메르센 소수라고 부릅니다.   \(p = 2\)라면, 메르센 소수는 \( M_2 = 2^2 - 1 = 4 - 1 = 3 \) 가 되어, 3은 가장 작은 메르센 소수가 됩니다.  \(p = 3\) 라면, 메르센 소수는 \( M_3 = 2^3 - 1 = 8 - 1 = 7 \) 가 됩니다.

그러나 모든 \(  2^p - 1 \)이 소수가 되는 것은 아닙니다. \(p=11\)의 경우에는 \( 2^{11} - 1 = 2048 - 1 = 2047 \) 이 되고, 2047은 \(23 \times 89\)로 표현할 수 있기 때문에 소수가 아닌 합성수입니다.

메르센 소수는 수학적으로 중요한 이유가 많은데, 특히 큰 소수를 찾는 데 매우 유용한 구조를 제공합니다.

문제 #97은 메르센 소수와는 약간 다른, 비(非)메르센 소수(Non-Mersenne Prime)에 관한 문제입니다. 주어진 숫자는 다음과 같은 형태를 가집니다:

\[ N = 28433 \times 2^{7830457} + 1 \]

이 숫자는 메르센 소수의 형태인 \(  2^p - 1 \) 과는 다르지만, 2의 거듭제곱을 포함하고 있습니다. 이 문제에서 해야 할 일은 이 매우 큰 숫자 N 의 마지막 10자리를 구하는 것입니다.

숫자가 엄청나게 크기 때문에 전체 값을 계산할 수 없으므로, “나머지 계산”이라는 수학적 기법을 활용해야 합니다. 마지막 10자리를 구하려면 \(  N \mod 10^{10} \) 를 계산하면 됩니다.

예를 들어, 12345 라는 숫자의 마지막 3자리를 알고 싶다면, 1000으로 나눈 나머지인 345가 나오는 방식입니다.

이 문제는 메르센 소수와 관련된 개념을 이해한 뒤, 비슷하지만 조금 더 복잡한 형태의 문제를 해결하는 데 도전하게 합니다.

 

big number calculation

 

제가 작성한 소스입니다.  사실 크게 프로그램 한 일은 없습니다.  효율을 위해서 오일러의 \(\varphi\) 함수를 이용하여 계산했습니다.  숫자가 커서 64비트 정수를 사용했습니다.

//------------------------------------------------
//    Project Euler #97 - Large Non-Mersenne Prime
//        - by Aubrey Choi
//        - created at 2015-04-14
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

int main()
{
    uint64_t p = 28433;
    uint64_t n = 7830457;
    uint64_t phi = 4;

    n -= 10;
    for( int i = 0 ; i < 9 ; i++ ) phi *= 5;
    n %= phi;
    n += 10;
    while( n-- )
    {
        p <<= 1;
        p %= 10000000000;
    }
    printf("%010ju\n", p+1);
}

 

코드의 목표는 \(  28433 \times 2^{7830457} + 1 \)의 마지막 10자리를 계산하는 것입니다. 이 숫자는 매우 크기 때문에, 모듈러 연산과 비트 연산을 사용해 효율적으로 계산합니다.

주요 부분 설명:

1. 초기화

uint64_t p = 28433;
uint64_t n = 7830457;
uint64_t phi = 4;

• p는 문제의 상수 값입니다.
• n은 거듭 제곱의 횟수입니다.
• phi는 오일러 피(phi) 함수 값 계산을 위한 변수입니다.

2. 모듈러스 최적화

n -= 10;
for (int i = 0; i < 9; i++) phi *= 5;
n %= phi;
n += 10;

• \(10^{10}\)의 오일러 피 함수 값을 계산하여 n을 더 작은 값으로 줄입니다.
• 이는 계산 범위를 줄여 효율성을 높이기 위한 것입니다.

3. 거듭 제곱 계산

while (n--) {
    p <<= 1;
    p %= 10000000000;
}

• p <<= 1은 p를 2배로 만드는 비트 연산입니다.
• p %= 10000000000은 \(10^{10}\)으로 나눈 나머지를 유지하여 숫자의 마지막 10자리만 계산합니다.
• n번 반복하여 \(2^n\)을 p에 반영합니다.

4. 결과 출력

printf("%010ju\n", p + 1);

• p+1을 출력하여 최종적으로 \(  28433 \times 2^{7830457} + 1 \)의 마지막 10자리를 구합니다.
• %010ju는 결과를 10자리로 포맷팅합니다(앞에 0을 채워줌).

n을 이분탐색해서 계산하는 방법의 소스도 추가합니다.

def modular_exponentiation(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        exponent = exponent // 2
        base = (base * base) % mod
    return result

mod = 10**10
power_mod = modular_exponentiation(2, 7830457, mod)
result = (28433 * power_mod + 1) % mod

print(result)