26. 프로젝트 오일러 #26 : 순환고리

이번 문제는 가장 긴 순환고리를 찾는 문제입니다.  사실 순환고리는 오일러의 수 문제로 귀결됩니다.  오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다.

라고 한다면,  오일러의 수는

이라고 할 수 있습니다.

즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다.  n이 소수라면 n-1 이 오일러의 수가 됩니다.

가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다.  10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 하나의 순환고리를 갖습니다.

일단 2의 배수와 5의 배수는 비순환고리를 가짐으로 실제 검사할 숫자들은입니다.  이 숫자 이외에는 비순환고리를 만듭니다.

예를 들어서 600의 순환고리의 길이가 k라면 300의 순환고리의 길이 역시 k입니다.  2와 5는 10의 약수이기 때문에 600의 순환고리의 길이와 3의 순환고리의 길이는 동일합니다.  즉, 짝수로 끝나는 수와 5로 끝나는 수는 검사할 필요가 없는 셈이죠.

사실 1000 미만인 수에서 순환고리의 길이 다 계산한다고 얼마나 느려질까요.  하지만 그 숫자가 늘어난다면요.  10개중 4개만 검사하는 것이 더 빠르겠죠.  그리고 비순환고리의 경우를 생각할 필요가 없으니까요.

그리고 두번째로 속도를 개선하기 위해서, 뒤 숫자부터 차례대로 계산을 해서 현재 계산된 최대 순환고리의 갯수가 검사하고자 하는 수보다 커지면 프로그램을 종료하게 하였습니다.

제시된 프로그램은 참고용으로만 보세요.

#include <stdio.h>

int main()
{
    int f[4] = { 1, 3, 7, 9 };
    int max = 6, v = 7;

    for( int i = 1000 ; i >= 10 ; i -= 10 )
    {
        if( i <= max ) break;
        for( int j = 0 ; j < 4 ; j++ )
        {
            int c = i-f[j];
            int k;
            int t = 10;
            for( k = 1 ; t != 1 ; k++ )
            {
                t = (t*10)%c;
            }
            if( k > max ) { max = k; v = c; }
        }
    }

    printf("Ans = %d(%d)\n", v, max);
}