Project Euler #3 - Largest prime factor

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

What is the largest prime factor of the number 600851475143 ?

출처: https://projecteuler.net/

600851475143의 소인수 중에서 가장 큰 수를 구하는 문제입니다.

루트값 까지만 계산하는 방법으로 시간 복잡도를 줄여 풀었습니다.

my solving

c++

#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> getPrimeFactor(ll n) 
{
    vector<ll> ret;
    ll sqrtn = ll(sqrt(n));
 
    for (ll i = 2; i <= sqrtn; i++)
    {
        while (n % i == 0) 
        {
            n /= i;
            ret.push_back(i);
        }
    }
 
    if (n > 1)
        ret.push_back(n);
    return ret;
}
 
int main() 
{
    vector<ll> frimes = getPrimeFactor(600851475143);
 
    cout << frimes.back() << endl;
 
    system("pause");
    return 0;
}