Number-Theory

LeetCode 3618 note: primality is about the index; a sieve of Eratosthenes marks all of 0..n-1 at once, faster than trial division per index

LeetCode 1979 note: find the minimum and maximum, then take their GCD with Euclid’s algorithm

LeetCode 952 note: sharing a factor ⇔ sharing a prime factor; factor each number and union indices with the same prime factor using Union-Find, with no pairwise GCDs

LeetCode 204 note: the sieve of Eratosthenes, crossing out multiples of each prime p starting at p², with the outer loop only up to √n

LeetCode 258 note: sum the digits repeatedly until one remains; the O(1) answer is the digital root 1 + (n - 1) % 9