[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\ne b$입니다.
예를 들어, $s(220)=284$이고 $s(284)=220$이므로 220과 284는 우애수입니다.
• 우애 체인(amicable chain)은 이러한 약수의 합 계산이 여러 수를 통해 이어지며 다시 원래 수로 돌아오는 경우를 말합니다.
예를 들어,  $a\to b\to c\to \cdots \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+\dots +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이고, 체인의 길이가 이전보다 길다면 업데이트합니다.