Project Euler - 문제 3번

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

 문제 3번 : 13195의 소인수는 5, 7, 13 그리고 29이다. 그러면, 600851475143의 가장 큰 소인수는 얼마인가?

---

 일단 문제는 간단합니다. 소인수분해를 해서 가장 큰 소인수를 찾는게 목표입니다. 그러면 먼저 소인수분해를 하면 될 것 같네요. 가장 일반적으로, 2를 제외한 모든 소수는 홀수이기 때문에, 먼저 주어진 숫자를 2로 나눠 홀수로 만듭니다. 그러나 이미 주어진 숫자는 홀수군요?

 이제 i=3부터 2씩 증가시키면서 mod를 취해 나머지가 0이면 주어진 숫자를 i로 나눠가면서 계속 소인수분해를 진행합니다. 어느 순간, 2씩 증가시키던 숫자 i가 소인수분해를 해 나가는 숫자와 같아지게 되고 이게 마지막 소수가 됩니다. 진행 과정상 마지막에 나오는 소인수가 가장 큰 소인수가 될 수밖에 없습니다.

 이 과정에서 단점은, 소수가 아닌 경우에도 mod를 취해서 나머지를 확인해 나간다는 점입니다. 약간의 시간이 더 걸리게 되는데 주어진 숫자가 그렇게 크진 않아서 시간은 매우 적게 걸렸습니다. 코드를 보면 이해가 쉬울 것 같네요.

#include <cstdlib>
#include <iostream>
#include "time.h"
using namespace std;

int main()
{
    clock_t start = clock();
  
    long long n = 600851475143;
    long long i; 
    
    while(n%2 == 0)
        n = n/2;
        
    for(i = 3; i != n; i += 2)
    {
     while(n%i == 0)
         n = n/i;
    }
    
    clock_t end = clock();
    cout << "결과 : " << i << endl;
    cout << "시간 : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

 그러면 결과가 아래와 같이 짠! 하고 나타납니다.

 중간에 실수를 좀 했었는데, 다행히도 이번에는 정답을 얻었습니다.