#3 : 가장 큰 소인수 찾기

이번 문제는 주어진 수에 대해서 가장 큰 소인수를 찾는 프로그램입니다.

 

사실 에라스토테네스의 체를 이용하여 가장 큰 소인수를 찾을 수밖에 없습니다.

 

일단 필요한 것은 주어진 수를 계속 나누기 하는 것입니다.  프로그램 역시 이 범주를 벗어나지 않습니다.

 

조금 속도를 빠르게 하기 위해서는 소수의 일반적인 형태, 2를 제외한 모든 소수는 홀수이다.

홀수 소인수는 6k+1, 6k+5를 가진다 등을 이용해서 시도횟수를 줄일 수는 있습니다.

 

이번에는 더 효율적인 알고리즘을 찾기 위한 방법은 별로 없어보이네요.

 

간단하게 프로그램을 짜보면 다음과 같습니다.

 

 

int main()
{
        int p = 3;
        int64 n = 600851475143;

        while( n%2 == 0 ) n /= 2;
        if( n == 1 ) { printf("Ans = 2\n"); return 0; }
        while( 1 )
        {
                while( n%p == 0 ) n /= p;
                if( n == 1 ) break;
                p += 2;
        }
        printf("Ans = %d\n", p);
        return 0;
}