euler-003.cpp

// ////////////////////////////////////////////////////////
// # Title
// Largest prime factor
//
// # URL
// https://projecteuler.net/problem=3
//
// # Problem
// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143?
//
// # Solved by
// Lyndsey Gu
// February 2023
//
// # Algorithm
// Each composite number `x` can be represented as the product of at least two factors: `x=factor*other`
// If we assume that `factor` is a prime number and `factor<=other`, then there are two options:
// 1. `other` can be a prime number, too
// 2. `other` is composite
//
// In case 1, `other` is the largest prime - and we are done.
// In case 2, we can continue the same process by setting set `x=other`.
// After some iterations we will hit case 1.
//
// Therefore I start a loop beginning with `factor=2` (the smallest prime)
// and as long as our number `x` can be divided by `factor` with remainder 0:
// - divide `x` by `factor`, but abort if `x==factor` because then we have found our largest prime factor.
//
// We can abort as soon as all `factor<=sqrt{x}` are processed because then only a prime is left.
//
// # Note
// You may have noticed that `factor` isn't always a prime number in my program:
// yes, I simply scan through all numbers, even composite ones.
//
// But if they are composite, then I already checked all smaller primes.
// That means, I checked all prime factors of that composite number, too.
// Therefore `x` can't be divided by a composite `factor` with remainder 0 because
// all required prime factors were already eliminated from `x`.
//
// In short: those divisions by composite numbers always fail but my program is still fast enough and
// writing a proper prime sieve doesn't give a significant speed boost for this problem.

#include <iostream>

using namespace std;

int main() {
    unsigned int tests;
    cin >> tests;

    while (tests--) {
        unsigned long long x;
        cin >> x;

        // x can be represented by x=factor*otherFactor
        // where factor <= otherFactor
        // therefore factor <= sqrt(x)
        for (unsigned long long factor = 2; factor * factor <= x; factor++)
        // remove factor, actually it's a prime
        // (can occur multiple times, e.g. 20=2*2*5)
        while (x % factor == 0 && x != factor) // note: keep last prime
            x /= factor;

        cout << x << endl;
    }
    
    return 0;
}