프로젝트 오일러(Project Euler) 3번문제

Problem 3

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

풀이

 보통 프로그래밍을 배우는 과정에서 "소수를 판별하는 법" 같은건 한번씩 거치는 과정이라 거기에 얽매이면 안되는 문제중 하나이다. 나도 처음에는 별 생각없이 막 숫자 하나씩 증가시키면서 이게 소순지 아닌지 판단하는 코드를 작성했는데 돌리자마자 이건 아니라는걸 체감하고 바로 다시 작성했다(시간이 너무 오래 걸린다). 

다시 문제를 살펴보면, 우리가 해야 할 건 소인수분해이다. 중학굔지 고등학굔지에서 배운 소인수 분해를 생각해보자 "15를 소인수분해 해라!" 라고하면 3으로 나누고 5라는 소수가 남았으니 3X5라고 쓰곤 했다. 위의 문제도 똑같이 만들어주면 된다. 다만 코드를 작성하면서 주의할건 600851475143이라는 수가 int형에는 담기지 않으니 long long형을 사용해 주어야 한다.

void main()
{
    long long num = 600851475143;
    int prime = 0;    // 가장 큰 소인수를 담을 변수
 
    for (int i = 3; i <= num; i++)    // 문제가 홀수기 때문에 3부터 시작
    {
        if (num % i == 0)    // i로 나눠지면
        {
            prime = i;    // 그 수를 소인수로 놓고
            num /= i;    // 숫자를 그 소수로 나눔
        }                // 위의 과정을 끝내면 현재 가장큰 소인수가 prime에 들어가게됨
    }
    printf("%d\n", prime);    
}

결과