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

largestprimefactor.cpp

#include <bits/stdc++.h>
#include <cassert>
using namespace std;

using ll = long long;

int sieve() {
    ll n = 600851475143;
    ll sz = sqrt(n);
    vector<bool> prime(sz, true);
    prime[1] = prime[2] = true;
    for (int i = 2; i < sz; i++)
        for (int k = i + i; k < sz; k += i)
            prime[k] = false;

    for (int i = sz - 1; i > 1; i--)
        if (prime[i] && n % i == 0)
            return i;

    return 1;
}

int main() {
    cout << sieve();
}