[C/C++] 프로젝트 오일러 #95 Amicable Chains(수학)

프로젝트 오일러 #95: Amicable Chains (우애 체인)

이 문제는 숫자들 사이의 관계를 탐구하는 것으로, 특정 수의 약수의 합을 계산하여 순환하는 우애 체인(amicable chain)을 찾는 것입니다. 다음과 같은 과정을 따릅니다:

1. 정의

• 어떤 수 \(n\)의 약수의 합을 \(s(n)\)이라고 정의합니다. 여기서 \(s(n)\)은 \(n\) 자신을 제외한 모든 양의 약수의 합입니다.
예를 들자면 \( s(12) = 1 + 2 + 3 + 4 + 6 = 16 \)으로   \( s(12) \) 값이 16이 됩니다.
• 두 수 \(a\)와 \(b\)가 우애수(amicable numbers)라면 \( s(a) = b \)이고 \(  s(b) = a  \)이며  \( a \neq b \)입니다.
예를 들어, \(  s(220) = 284 \)이고 \(  s(284) = 220 \)이므로 220과 284는 우애수입니다.
• 우애 체인(amicable chain)은 이러한 약수의 합 계산이 여러 수를 통해 이어지며 다시 원래 수로 돌아오는 경우를 말합니다.
예를 들어,  \( a \to b \to c \to \dots \to a \)와 같은 형식으로 순환합니다.

2. 목표

1.  \( n < 10^6 \)인 수들에 대해 우애 체인을 탐색합니다.
2. 가장 긴 우애 체인을 구성하는 수열을 찾습니다.
3. 이 체인의 최소값을 구합니다.

3. 예제

•  \( n = 12496 \)부터 시작한다고 가정합니다:
• \(  s(12496) = 14288 \)
• \(  s(14288) = 15472  \)
• \(  s(15472) = 14536 \)
• \(  s(14536) = 14264 \)
• \(  s(14264) = 12496 \)

이 체인은 \(  12496 \to 14288 \to 15472 \to 14536 \to 14264 \to 12496 \)로 다시 순환하며, 길이는 5입니다.

 

number chains

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #95 - Amicable Chains
//        - by Aubrey Choi
//        - created at 2015-10-23
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    LIMIT    1000000
#define    RLIMIT    1000

int primes[RLIMIT];
int pcount = 0;

int sigma1(int n)
{
    int v = 1;
    for( int i = 0 ; i < pcount && n > 1 ; i++ )
    {
        if( n%primes[i] ) continue;
        int s = 1;
        while( n%primes[i] == 0 ) { s = s*primes[i]+1; n /= primes[i]; }
        v *= s;
    }
    return (n>1)?v*(1+n):v;
}

void solve1()
{
    primes[pcount++] = 2;
    primes[pcount++] = 3;
    for( int p = 5 ; p <= RLIMIT ; p++ )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime ) primes[pcount++] = p;
    }

    static char flag[LIMIT+1];

    int value = 1, length = 1;
    for( int n = 2 ; n < LIMIT ; n++ )
    {
        memset(flag, 0, sizeof(flag));
        int q = n, t = 0;
        do
        {
            flag[q] = 1;
            q = sigma1(q)-q;
            t++;
        } while( q <= LIMIT && flag[q] == 0 );
        if( q == n && t > length ) { value = q; length = t; printf("%d(%d)\n", q, t); }
    }
    printf("Ans = %d(%d)\n", value, length);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

코드의 각 부분을 설명하겠습니다.

1. 매크로 정의

#define LIMIT 1000000
#define RLIMIT 1000

• LIMIT: 문제에서 요구하는 범위의 상한 .
• RLIMIT: 소수 계산에 사용할 상한  (최적화를 위한 제한).

2. 전역 변수

int primes[RLIMIT];
int pcount = 0;

• primes: 소수를 저장하는 배열.  이하의 모든 소수가 이 배열에 저장됩니다.
• pcount: 소수의 개수를 추적하는 변수.

3. 약수의 합 계산 함수: sigma1

int sigma1(int n)
{
    int v = 1;
    for( int i = 0 ; i < pcount && n > 1 ; i++ )
    {
        if( n%primes[i] ) continue;
        int s = 1;
        while( n%primes[i] == 0 ) { s = s*primes[i]+1; n /= primes[i]; }
        v *= s;
    }
    return (n>1)?v*(1+n):v;
}

• 약수의 합 \( \sigma(n) \)을 계산합니다.
• 주어진 숫자 \( n \)을 소인수분해하여 소인수 \( p \)의 거듭제곱 합 공식을 이용해 \( \sigma(n) \)을 효율적으로 계산:

 

\[ \sigma(n) = \sum_{p|n} (1 + p + p^2 + \ldots + p^k) \]

• 반환값은 \(n\)을 포함한 약수의 합으로, \(n\) 자신을 제외하려면 \(n\)을 빼야 합니다.

예를 들어, \( n = 12 \) 일 때,
• 약수: \(  1, 2, 3, 4, 6, 12 \)
•  \( \sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 \)
• \(  s(12) = 28 - 12 = 16 \)

4. 소수 생성 함수: solve1

primes[pcount++] = 2;
primes[pcount++] = 3;
for( int p = 5 ; p <= RLIMIT ; p++ )
{
    bool isPrime = true;
    for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
        if( p%primes[i] == 0 ) { isPrime = false; break; }
    if( isPrime ) primes[pcount++] = p;
}

•  RLIMIT 이하의 모든 소수를 생성하고 primes 배열에 저장합니다.
• 소수를 찾기 위해 에라토스테네스의 체 대신 간단한 나눗셈 검사를 사용하였습니다.

5. 우애 체인 탐색

static char flag[LIMIT+1];

• flag 배열은 특정 숫자를 체인 내에서 방문했는지 여부를 기록합니다.
• 매번 새로운 숫자로 시작할 때 flag 배열을 초기화(memset)합니다.

int q = n, t = 0;
do
{
    flag[q] = 1;
    q = sigma1(q)-q; // 약수의 합에서 자신을 제외
    t++;
} while( q <= LIMIT && flag[q] == 0 );

• n 에서 시작하여 약수의 합을 반복적으로 계산하여 체인을 생성합니다.
• 만약 이전에 방문한 숫자가 나오면 순환이 발생합니다.

if( q == n && t > length )
{
    value = q;
    length = t;
    printf("%d(%d)\n", q, t);
}

• 순환이 시작점으로 돌아온다면 q == n이고, 체인의 길이가 이전보다 길다면 업데이트합니다.