[C++]프로젝트 오일러 3번 문제&풀이 (가장 큰 소인수 구하기)

문제

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

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

 

접근방법

1. 1부터 차례로 증가시키며 계산하되,

2. 해당 숫자로 나눠지면 계속 나누고, 안 나눠지면 그 때 증가시킨다.

3. 마지막으로 나누었을 때 1이 되도록 하는 값이 우리가 구하고자 하는 값이다.

 

#include <iostream>

using namespace std;

int main()
{
    __int64 num = 600851475143;
    int i = 2;

    while (num != 1)
    {
        if (num % i == 0)
        {
            num /= i;
            //cout << i << "\t" << num << endl;
        }
        else
            i++;
    }
    cout << "Answer is : " << i << endl;

    return 0;
}

참고

mannlim/ProjectEuler