Math & Number Theory

Number theory problems hand you a number instead of a collection, so the size of the input is its value. A loop over every value up to $n$ is already too slow at $n = 10^9$, and the work is finding the identity or the factorization that makes the loop unnecessary.

	C++	Python	Java
$\gcd(a, b)$	std::gcd	math.gcd	BigInteger.gcd
$a^b \bmod m$	none built in	pow(a, b, m)	BigInteger.modPow
Primes up to $n$	none built in	none built in	none built in

Most of these take only a few lines to write by hand. The real trap is intermediate overflow, where the final answer fits in a 32-bit int but multiplying two values near $10^9$ overflows along the way. That is why modular exponentiation reduces after every squaring, and why lcm is written a / gcd(a, b) * b with the division first.

Task	Naive	The tool
$\gcd(a, b)$	Trial division, $O(\min(a,b))$	Euclid, $O(\log \min(a,b))$
$a^b \bmod m$	$b$ multiplications	Square-and-multiply, $O(\log b)$
Primes up to $n$	Test each, $O(n \sqrt{n})$	Sieve, $O(n \log \log n)$

Reach for these when a problem turns on divisibility, digits, remainders, or how often a factor appears, where the answer follows from how a number is built rather than from scanning data.

The problems below start with carries and digit arithmetic, move through an arithmetic-series identity, Euclid's algorithm, and fast powers under a modulus, and end with the sieve and a factorial's prime factors.