Problem 003

Problem 003 : Largest prime factor (5%)

link

Description

original

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

간략해석

600851475143의 가장 큰 소인수.

Idea & Algorithm

naive idea

약 $6\cdot10^{13}$이므로 $8\cdot10^6$정도의 연산을 하면 가장 큰 소인수를 구할 수 있다.

advanced idea

하지만 만약 이 수의 소인수가 여러개인 경우에 대해서는 계속 찾은 소인수를 나눠주면서 수를 작게 만들어준다면 더 빠르게 해결할 수 있다.

source code

#include <stdio.h>
#define ll long long

int main(){
    ll num = 600851475143;
    ll p = 2;
    ll maxp = 2;
    // num에 따라서 시간이 매우 커질 수도 있으니, p의 크기 제한.
    while(num>=p && p < 8000000){
        if(num%p==0){
            maxp = p;
            num /= p;
        }
        else{
            p++;
        }
    }
    printf("%lld",maxp);
}