On this page

Number Theory I: Divisibility, Primes, GCD & Sieves

Two gears mesh, one with 12 teeth and one with 18. After how many turns are the same two teeth touching again? A recipe serves 6 and you need it for 4: what is the simplest fraction to scale by? A website needs every prime below ten million, now, in under a second. A key generator needs a number with leaving remainder 1 when divided by 3120.

All four are number theory: the study of the integers — whole numbers like — and of how they divide one another. It is the oldest branch of mathematics that still runs inside every computer you own. Euclid's algorithm for the greatest common divisor is about 2,300 years old and it is still the fastest simple way to reduce a fraction, compute an RSA key or check whether two numbers share a factor. The sieve of Eratosthenes is about as old and it still generates prime tables in milliseconds.

This lesson builds the toolkit from scratch: divisibility, primes, GCD and LCM, the extended Euclidean algorithm, equations of the form , three sieves, and factorization with the divisor-count and divisor-sum formulas that fall out of it. The next lesson, Modular Arithmetic, uses all of it: modular inverses are extended Euclid, Euler's totient is a factorization, and the Chinese Remainder Theorem is Bézout's identity in disguise.

You need only school arithmetic, the idea of from Complexity Analysis and proof by induction from Recursion & Induction.

Why this exists

Programmers meet number theory in three places.

  1. Interview and contest problems. "Count primes below ", "reduce this fraction", "can two jugs of 3 and 5 litres measure exactly 4?", "how many divisors does have?", "find the smallest number divisible by every element". Each has a one-line brute force that times out and a number-theoretic answer that runs in microseconds.
  2. Systems code. Rational arithmetic (Python's fractions.Fraction normalises every result with a GCD), hash tables with prime-sized bucket arrays, periodic schedulers that need the least common multiple of task periods, image and video code reducing aspect ratios (1920×1080 → 16:9 is a division by ).
  3. Cryptography. RSA, Diffie–Hellman and elliptic-curve cryptography are number theory with very large numbers. Key generation calls extended Euclid; prime generation starts by trial-dividing candidates by a table of small primes before running the expensive probabilistic test.

The two oldest algorithms in this lesson come from ancient Greece. Euclid's Elements (Book VII, around 300 BC) describes the GCD algorithm by repeated subtraction. Eratosthenes of Cyrene (around 240 BC) is credited with the sieve. Gabriel Lamé proved in 1844 that Euclid's algorithm takes a number of steps at most about five times the number of decimal digits of the smaller input — usually cited as the first serious analysis of an algorithm's running time, and the first practical application of the Fibonacci numbers. The linear sieve that finds every number's smallest prime factor in is much younger: Gries and Misra published a linear-time sieve in 1978.

Pattern triggers

If the problem says or has…Think of…
"simplify the fraction", "reduce the ratio", "largest tile that fits both sides"GCD
"when do two cycles line up again", "smallest number divisible by all of"LCM (divide first)
"can you measure exactly litres with jugs and ", "reachable amounts with steps and "Bézout: must be a multiple of
"find integers with ", "integer point on a line"Extended Euclid + linear Diophantine equation
"inverse of modulo "Extended Euclid (next lesson: Modular Arithmetic)
"count / list primes up to " with or soSieve of Eratosthenes
"primes in " with up to and up to Segmented sieve
Many queries "factorize " for Linear sieve storing smallest prime factor (SPF)
One number (or so) to factorizeTrial division up to
"number of divisors", "sum of divisors", "is a perfect square / cube"Factorize, then and
"GCD of a subarray", "GCD of all pairs"GCD is associative; it can only drop times along a prefix
Factorize a 64-bit or larger numberNot this lesson: Pollard's rho in Number Theory II
"is this 64-bit number prime?" (one query)Miller–Rabin (Randomized Algorithms)

Intuition & first principles

Divisibility

We say divides , written , when for some integer . So (because ), , and every integer divides (because ). When , is a divisor (or factor) of and is a multiple of .

Three facts follow straight from the definition, and every proof in this lesson uses them:

  1. If and , then and . (Write , ; then .)
  2. More generally, if and , then for any integers .
  3. If and , then .

Division with remainder. For any integer and positive integer there are unique integers (quotient) and (remainder) with

In code, is a // b and is a % b in Python. For non-negative every language agrees. For negative they do not — C++, Java and JavaScript give a negative remainder for a negative — and the next lesson spends a whole section on that trap. In this lesson we keep inputs non-negative unless we say otherwise.

Primes

A prime is an integer whose only positive divisors are and : . An integer that is not prime is composite. is neither: excluding it is what makes the next theorem have exactly one answer.

Fundamental theorem of arithmetic. Every integer can be written as a product of primes, and that product is unique up to the order of the factors:

For example . This prime factorization is the "DNA" of a number: divisors, GCDs, LCMs and Euler's totient can all be read off it.

Two cheap but important consequences:

  • A composite has a prime factor . If with , then , so , and any prime factor of is even smaller. This is why trial division stops at and why the sieve only needs primes up to .
  • There are infinitely many primes (Euclid). If were all of them, leaves remainder 1 when divided by each, so its prime factors are none of them — a contradiction.

How many primes are there? Write (the Greek letter pi, here a function name, not 3.14) for the number of primes . The prime number theorem says . Exact values are worth memorising as test oracles; every sieve you write should reproduce them:

4251681,2299,59278,498664,5795,761,455
4.321.7144.81,085.78,685.972,382.4620,420.75,428,681.0

(The values up to were recomputed for this page with a sieve; is the standard value from OEIS A006880.) So roughly 1 in 14 numbers near a million is prime, and 1 in 23 near : primes thin out, but slowly. That slow thinning is why "pick random 1024-bit odd numbers until one is prime" finishes after a few hundred tries.

The greatest common divisor

The greatest common divisor is the largest integer that divides both and . So , , , and by convention . Two numbers with are coprime (or relatively prime): they share no prime factor.

The obvious algorithm — try every from down to 1 — takes up to steps: a billion steps for numbers around a billion. Factoring both numbers and taking the common primes with the smaller exponents works (, , ) but factoring is hard for big numbers. Euclid's insight avoids factoring entirely.

The key identity. For :

Why it is true. Write with . Any that divides and also divides (fact 2 above with ). Any that divides and also divides . So the pairs and have exactly the same set of common divisors, and therefore the same greatest one.

Each step replaces the pair by a smaller pair with the same answer. Eventually the second number is , and .

A picture that makes it obvious: you want to tile a rectangle with the largest possible equal squares. Cut off as many squares as fit (two), leaving a strip. Any square that tiles the original also tiles the strip, and vice versa. Repeat on the strip. When the cut leaves nothing, the last square size tiles everything.

Least common multiple

The least common multiple is the smallest positive integer divisible by both. The two gears with 12 and 18 teeth realign after teeth have passed: 3 turns of the small gear, 2 of the big one.

From the factorizations, the GCD takes the minimum exponent of each prime and the LCM takes the maximum. Since ,

So — but never compute it in that order in a fixed-width language. With , is right at the edge of a signed 64-bit integer, even though the LCM is just . Divide first:

which only overflows when the answer itself does.

Mechanics

1. Euclid's algorithm, traced

:

StepNext pair
1252105242(105, 42)
210542221(42, 21)
3422120(21, 0)
—210stop:

Check: and , common part . Three steps instead of 105 trial divisions.

flowchart LR
    A["(252, 105)"] -->|"252 = 2·105 + 42"| B["(105, 42)"]
    B -->|"105 = 2·42 + 21"| C["(42, 21)"]
    C -->|"42 = 2·21 + 0"| D["(21, 0)"]
    D --> G["gcd = 21"]

The code is three lines:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

If the first step just swaps them (), so no special case is needed.

2. How many steps? Lamé's theorem and the Fibonacci worst case

Quick bound. After two steps the first number at least halves. Take a step from to with . If , then the new first number is already at most half of . If , then and , so after one more step the first number is . Either way, two steps at least halve the first number, so Euclid takes at most steps: about 60 steps for 30-bit numbers, about 128 for 64-bit numbers.

The exact worst case. What inputs make Euclid as slow as possible? Each step should make as little progress as possible, which means every quotient should be 1: . Run that backwards from the end, : the pairs are — consecutive Fibonacci numbers , .

Lamé's theorem (1844). If Euclid's algorithm on takes division steps, then and .

Proof by induction on . For : and gives . For the inductive step, the first division turns into , which needs more steps, so by the hypothesis and . Since with , .

Since with the golden ratio , : at most about steps, which is Lamé's "five times the number of digits". For inputs up to 100 the slowest pair is with 9 steps; takes 10. The full cost is divisions. For huge numbers (thousands of digits), each division costs more, and the total bit cost is by a telescoping argument (Knuth, TAOCP vol. 2, §4.5.3).

3. Extended Euclid and Bézout's identity

Run Euclid and keep track of how each remainder is built from the original and . You get more than the GCD: two integers with

Bézout's identity says such always exist. These coefficients are the single most useful by-product in elementary number theory: they give modular inverses (next lesson), solve , and construct Chinese-remainder solutions.

The recursive version. Suppose the recursive call already found with . Substitute :

So and . The base case is , so .

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

The iterative version (no recursion depth, same answer). Maintain the invariant that every remainder in the sequence satisfies . Start with and . Each new remainder is , so the coefficients obey the same rule: and .

Trace for , :

RowCheck
0—24010240
1—460146
25101−5
346−421
4145−26
512−947
62023−120

The last non-zero remainder is , with . The recursive version returns the same .

Notice row 6: . In general the final row is , and adding any multiple of it to a solution gives another solution. That is exactly the "general solution" of the next section.

flowchart TD
    S["Start: r0 = a, r1 = b, with coefficients (1,0) and (0,1)"] --> L{"r1 = 0?"}
    L -->|"no"| Q["q = r0 div r1"]
    Q --> U["(r0, r1) = (r1, r0 - q·r1), same update for s and for t"]
    U --> L
    L -->|"yes"| R["gcd = r0, x = s0, y = t0"]

Size of the coefficients. The returned satisfy and (for not dividing one another), so they fit in the same integer type as the inputs. No overflow surprises here — overflow appears only when you scale them, as in the next section.

4. Linear Diophantine equations

A Diophantine equation (after Diophantus of Alexandria) is one where only integer solutions count. The linear one in two unknowns is solved completely by extended Euclid.

When does a solution exist? Let . Whatever integers you choose, divides (fact 2). So if , there is no solution. If , take Bézout's and multiply by :

All solutions. If is one solution, every solution is

Why. Plug in: , so these are solutions. Conversely, if is any solution, subtracting gives ; divide by : . Since and are coprime, must divide (this step is Euclid's lemma: if and , then — proved by multiplying Bézout's by ). So for some , and follows.

Worked example: . divides 6, so solutions exist. From the trace, ; multiply by : , . Check: . The step sizes are and , so every solution is . The smallest non-negative is at : , (check: ).

The water-jug puzzle. Jugs of 3 and 5 litres, can you measure exactly 4? Measurable amounts are (fill one jug times, empty the other times), and divides 4, so yes — provided , the total capacity. With jugs of 6 and 10 you can never measure an odd amount.

Overflow when scaling

can be as large as . With near that overflows 64 bits even though a small solution exists. Reduce first: since solutions repeat every in , compute with a safe 128-bit multiply, then derive . The Modular Arithmetic lesson covers safe mulmod.

5. The sieve of Eratosthenes

To list all primes up to : write down . The smallest unmarked number, 2, is prime; cross out all its multiples. The next unmarked number, 3, is prime (nothing smaller divides it); cross out its multiples. Continue. Every number still unmarked at the end is prime.

Two refinements make it fast:

  • Start crossing at . Any multiple with has a prime factor smaller than (a factor of ), so it was already crossed out by that smaller prime. The first multiple of that is new is .
  • Stop at . Once , there is nothing left to cross out. Every composite has a prime factor , so it is already marked.

Trace for (, so only cross anything out):

Crossed out (start at , step )Newly compositeStill unmarked after this pass
24, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 3014 numbers2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
39, 12, 15, 18, 21, 24, 27, 309, 15, 21, 272 3 5 7 11 13 17 19 23 25 29
525, 30252 3 5 7 11 13 17 19 23 29
7: stop

Ten primes, matching . There were 24 crossings for 19 composites: 12, 18, 24 and 30 were crossed twice, 30 by all three primes. That repetition is the factor.

Running time: . The prime crosses out about numbers. The total is

using Mertens' second theorem: the sum of over primes is . The factor is tiny: . In practice the sieve is limited by memory traffic, not arithmetic: a byte per number for is 100 MB, and the inner loop jumps through it with stride , missing the cache. Two fixes: store only odd numbers (halves memory and time), use one bit per number (a bitset or bytearray slice), or sieve in cache-sized blocks — which is exactly the segmented sieve below.

flowchart TD
    I["is_prime[0..n] = true, except 0 and 1"] --> P["p = 2"]
    P --> C{"p·p <= n?"}
    C -->|"no"| D["Done: unmarked numbers are prime"]
    C -->|"yes"| M{"is_prime[p]?"}
    M -->|"yes"| X["mark p·p, p·p+p, ... up to n as composite"]
    M -->|"no"| N["p = p + 1"]
    X --> N
    N --> C

6. The segmented sieve: primes in

To find the primes between and you cannot allocate flags. You do not need to. Every composite in has a prime factor . So:

  1. Sieve the base primes up to with an ordinary sieve.
  2. Allocate one flag per number in (here flags).
  3. For each base prime , cross out its multiples in the window, starting at .

Time , memory . The first primes above are and , and there are 49 primes in — both used as tests in the implementation below. The same idea with chopped into blocks of about 32 KB sieves in cache, which is how fast prime-generation libraries such as Kim Walisch's primesieve work.

7. The linear sieve and smallest prime factors

The Eratosthenes sieve crosses 30 out three times. A linear sieve crosses out each composite exactly once, which gives time and — more usefully — records each number's smallest prime factor for free.

Idea. Every composite has exactly one representation where is the smallest prime factor of . Note that then (all of 's prime factors are factors of , so they are at least ). The linear sieve generates each composite through exactly this pair: for every from 2 to , and for every prime , set .

spf = [0] * (n + 1)
primes = []
for i in range(2, n + 1):
    if spf[i] == 0:              # nobody crossed i out: it is prime
        spf[i] = i
        primes.append(i)
    for p in primes:
        if p > spf[i] or i * p > n:
            break
        spf[i * p] = p            # p is the smallest prime factor of i*p

Trace for (i is the outer loop, each entry x←p means "set spf(x) = p"):

spf()prime list afterMarks made
22 (new prime)24←2
33 (new prime)2, 36←2, 9←3
422, 38←2 (stop: next prime 3 > spf(4) = 2)
55 (new prime)2, 3, 510←2, 15←3 (stop: 25 > 20)
6212←2
77 (new prime)2, 3, 5, 714←2 (21 > 20)
8216←2
9318←2 (27 > 20)
10220←2
11–2011, 13, 17, 19 addednone ()

Final table, index 2 to 20: spf = 2 3 2 5 2 7 2 3 2 11 2 13 2 3 2 17 2 19 2. Every composite from 4 to 20 got exactly one mark: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20 — eleven composites, eleven marks. Compare Eratosthenes on : 12 gets crossed by 2 and by 3, 18 by 2 and by 3.

Why . Count the inner-loop iterations that write something. A write sets only when , and then really is the smallest prime factor of . So the pair that writes is forced: and . Each composite is therefore written exactly once. The only other iterations are the single breaking iteration per . Total work: (number of composites) + (number of ) .

Linear vs Eratosthenes in practice. The linear sieve does fewer writes but stores an integer per number (4 bytes) instead of a bit or byte, and its inner loop has a branch per step. For "just count primes", a well-written Eratosthenes (bitset, odd-only, segmented) is faster in practice; the linear sieve wins when you want the SPF table — for fast factorization of many numbers, or to compute multiplicative functions like Euler's totient (see Modular Arithmetic) and the Möbius function in the same pass.

8. Factorization

Trial division. Divide by while ; whenever , divide it out completely and record the exponent. Whatever is left above 1 at the end is a prime (it has no factor its square root). Composite never divide the remaining because their prime factors were already removed. Cost : divisions for , a few milliseconds. Testing only 2 and then odd halves the work; testing only after 2 and 3 cuts it to a third.

Trace for :

beforeDivides?Exponent after
2360yes, three times345
345yes, twice25
45: stop5
—5leftover prime11

So .

With an SPF table. If the sieve limit, factorization is just "divide by until 1". Every division at least halves , so it is per query: at most 23 divisions for . For queries on numbers up to this is the difference between and operations.

9. Divisor count and divisor sum from the factorization

A divisor of chooses, for each prime, an exponent from to — choices, independently. So the number of divisors is

and expanding the product produces every divisor exactly once, so the sum of divisors is

For : and (both checked against a brute-force divisor list).

How big can get? Much smaller than people expect. The most divisors for is 64 (); for it is 240 (); for it is 1,344 (); for it is 103,680 () (OEIS A066150; the factorizations and divisor counts were checked for this page). So "loop over all divisors of " is cheap even when is huge — as long as you can factor . A common rule of thumb is for in the contest range.

To list all divisors, either combine the prime powers (recursively, outputs) or loop from 1 to and output and for each (careful not to output twice for a perfect square).

Divisor sieve. To get for every , loop over each and add 1 to all its multiples: (the harmonic series). It is simpler than the SPF route and fine up to or .

The ladder: brute force → better → optimal

Two problems, two ladders.

Ladder A:

RungMethodTimeWhy it is better
1Try every from down to 1— (a billion steps at )
2Factor both, take common primes with min exponentsSquare-root, but factoring big numbers is hard
3Subtractive Euclid: , up to No factoring; still slow when one number is tiny ( takes subtractions)
4Euclid with remaindersEach mod does all the subtractions at once
sideBinary GCD (Stein, 1967): strip common factors of 2, then subtract odd from odd and shift shifts/subtractionsNo division instruction; useful on hardware where division is slow and for multi-word big integers

Ladder B: all primes up to

RungMethodTime for (order of magnitude)Notes
1Test each by trying every divisor — Hopeless
2Test each by trial division up to — (fewer in practice: composites exit early)Too slow beyond
3Sieve of Eratosthenes from , up to — The standard choice
4Linear sieve (Gries–Misra) — Same speed or slower in practice for counting, but gives SPF
5Segmented, odd-only, bit-packed Eratosthenes, memoryFastest in practice, scales to and beyond

To count primes up to or without listing them there are sub-linear algorithms (Legendre, Meissel–Lehmer, Lucy_Hedgehog's method). They build on the divisor-block technique of Number Theory II, which sketches them; cp-algorithms and Lagarias–Miller–Odlyzko (1985) have the details.

Correctness

Euclid's algorithm. Invariant: the GCD of the current pair equals of the original pair. It holds at the start trivially and is preserved by each step (the key identity, proved above). Termination: the second component is a non-negative integer that strictly decreases (), so it reaches 0. At exit, the pair is and .

Extended Euclid. Invariant: for both rows currently kept. True for rows 0 and 1 by construction; the update is linear, so applying the same update to and preserves it. At exit the kept remainder is the GCD (by the Euclid argument), so is a Bézout pair.

Sieve of Eratosthenes. Claim: at the end, is_prime[k] is true exactly when is prime (). A prime is never marked, because every marked number is with , hence composite. A composite has a smallest prime factor , and with (as is the smallest factor), so and is in the range crossed out when the outer loop reaches . When the loop reaches , is_prime[p] is still true (it is prime), so the marking happens.

Linear sieve. Claim: spf[x] ends as the smallest prime factor of every . For primes: nobody writes spf[p] before the outer loop reaches (a write to needs , so is composite), so the loop detects as prime. For a composite with and : is processed earlier, and , so the inner loop for reaches (all primes are already in the list because ) and writes spf[x] = q. Uniqueness of the write was shown in the complexity argument.

Trial division. Invariant: when the loop reaches , the remaining has no prime factor . Hence if , is prime (a composite would have a smaller prime factor dividing ). If the loop ends with , the remaining has no prime factor , so it is prime.

Complexity

OperationTimeSpaceNotes
gcd(a, b) divisionsWorst case: consecutive Fibonacci numbers
lcm(a, b)same as gcdDivide before multiplying
ext_gcd(a, b) iterative, recursive stackCoefficients bounded by and
gcd of an array of numbers up to totalAmortized: the running gcd only shrinks, each real shrink at least halves it
Eratosthenes up to bits or bytesMemory-bound past ~
Segmented sieve on Block size ~ L1/L2 cache
Linear sieve with SPF up to integers40 MB for with 4-byte ints
Factorize by trial division worst (n prime or semiprime) outputFast when has small factors
Factorize with SPF table—Needs sieve limit
, from factorization for distinct primes— for
Divisor-count sieve up to Harmonic sum

The gcd-of-an-array bound is a nice amortized argument: each call gcd(running, x) costs , and the logs telescope to at most over the whole array.

Implementation

Both code groups are complete programs that test themselves against the numbers in this lesson (and against brute force). Every snippet was run on Python 3.12, Java 21, C++17 (g++) and Node 24 before publishing.

GCD, LCM, extended Euclid, Diophantine equations

from math import gcd as math_gcd


def gcd(a: int, b: int) -> int:
    """Euclid's algorithm. Works for any integers; result is >= 0."""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a


def lcm(a: int, b: int) -> int:
    """Divide before multiplying (matters in fixed-width languages)."""
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)


def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Iterative extended Euclid for a, b >= 0: returns (g, x, y) with a*x + b*y == g."""
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y


def ext_gcd_rec(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd_rec(b, a % b)
    return g, y1, x1 - (a // b) * y1


def diophantine(a: int, b: int, c: int):
    """One solution (x0, y0) of a*x + b*y == c and the steps (dx, dy):
    all solutions are (x0 + dx*t, y0 - dy*t). Returns None if none exist."""
    if a == 0 and b == 0:
        return (0, 0, 0, 0) if c == 0 else None
    g, x, y = ext_gcd(abs(a), abs(b))
    if c % g != 0:
        return None
    if a < 0:
        x = -x
    if b < 0:
        y = -y
    return x * (c // g), y * (c // g), b // g, a // g


def euclid_steps(a: int, b: int) -> int:
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return steps


if __name__ == "__main__":
    assert gcd(252, 105) == 21 and gcd(12, 18) == 6 and gcd(7, 0) == 7 and gcd(0, 0) == 0
    assert gcd(-12, 18) == 6
    assert lcm(12, 18) == 36 and lcm(3 * 10**9, 3 * 10**9) == 3 * 10**9
    assert ext_gcd(240, 46) == (2, -9, 47) == ext_gcd_rec(240, 46)
    x0, y0, dx, dy = diophantine(240, 46, 6)
    assert (x0, y0, dx, dy) == (-27, 141, 23, 120)
    assert 240 * (x0 + 2 * dx) + 46 * (y0 - 2 * dy) == 6 and x0 + 2 * dx == 19
    assert diophantine(6, 10, 7) is None            # gcd 2 does not divide 7
    x0, y0, _, _ = diophantine(-4, 6, 10)
    assert -4 * x0 + 6 * y0 == 10
    assert euclid_steps(89, 55) == 9 and euclid_steps(144, 89) == 10
    import random
    for _ in range(2000):                           # cross-check against the library
        a, b = random.randrange(10**12), random.randrange(10**12)
        g, x, y = ext_gcd(a, b)
        assert g == math_gcd(a, b) and a * x + b * y == g
        assert g == 0 or abs(x) <= max(1, b // g) and abs(y) <= max(1, a // g)
    print("gcd tests passed")
import java.math.BigInteger;
import java.util.Random;

public class GcdFamily {
    static long gcd(long a, long b) {
        a = Math.abs(a); b = Math.abs(b);
        while (b != 0) { long t = a % b; a = b; b = t; }
        return a;
    }

    static long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        return Math.abs(a / gcd(a, b) * b);           // divide first
    }

    /** Iterative extended Euclid for a, b >= 0: returns {g, x, y} with a*x + b*y == g. */
    static long[] extGcd(long a, long b) {
        long oldR = a, r = b, oldX = 1, x = 0, oldY = 0, y = 1;
        while (r != 0) {
            long q = oldR / r, t;
            t = oldR - q * r; oldR = r; r = t;
            t = oldX - q * x; oldX = x; x = t;
            t = oldY - q * y; oldY = y; y = t;
        }
        return new long[]{oldR, oldX, oldY};
    }

    /** {x0, y0, dx, dy} with all solutions (x0 + dx*t, y0 - dy*t), or null. */
    static long[] diophantine(long a, long b, long c) {
        if (a == 0 && b == 0) return c == 0 ? new long[]{0, 0, 0, 0} : null;
        long[] e = extGcd(Math.abs(a), Math.abs(b));
        long g = e[0], x = e[1], y = e[2];
        if (c % g != 0) return null;
        if (a < 0) x = -x;
        if (b < 0) y = -y;
        // Math.multiplyExact throws instead of silently overflowing
        return new long[]{Math.multiplyExact(x, c / g), Math.multiplyExact(y, c / g), b / g, a / g};
    }

    static int euclidSteps(long a, long b) {
        int s = 0;
        while (b != 0) { long t = a % b; a = b; b = t; s++; }
        return s;
    }

    public static void main(String[] args) {
        if (gcd(252, 105) != 21 || gcd(12, 18) != 6 || gcd(7, 0) != 7 || gcd(-12, 18) != 6)
            throw new AssertionError("gcd");
        if (lcm(12, 18) != 36 || lcm(3_000_000_000L, 3_000_000_000L) != 3_000_000_000L)
            throw new AssertionError("lcm");
        long[] e = extGcd(240, 46);
        if (e[0] != 2 || e[1] != -9 || e[2] != 47) throw new AssertionError("extGcd");
        long[] d = diophantine(240, 46, 6);
        if (d[0] != -27 || d[1] != 141 || d[2] != 23 || d[3] != 120) throw new AssertionError("dio");
        if (diophantine(6, 10, 7) != null) throw new AssertionError("dio none");
        long[] n = diophantine(-4, 6, 10);
        if (-4 * n[0] + 6 * n[1] != 10) throw new AssertionError("dio neg");
        if (euclidSteps(89, 55) != 9 || euclidSteps(144, 89) != 10) throw new AssertionError("lame");
        Random rnd = new Random(1);
        for (int i = 0; i < 2000; i++) {
            long a = Math.floorMod(rnd.nextLong(), 1_000_000_000_000L);
            long b = Math.floorMod(rnd.nextLong(), 1_000_000_000_000L);
            long[] r = extGcd(a, b);
            if (r[0] != BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValueExact())
                throw new AssertionError("vs BigInteger");
            // a*x + b*y == g, checked in BigInteger because a*x can exceed 64 bits mid-way
            BigInteger lhs = BigInteger.valueOf(a).multiply(BigInteger.valueOf(r[1]))
                    .add(BigInteger.valueOf(b).multiply(BigInteger.valueOf(r[2])));
            if (!lhs.equals(BigInteger.valueOf(r[0]))) throw new AssertionError("bezout");
        }
        System.out.println("gcd tests passed");
    }
}
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <numeric>   // std::gcd, std::lcm (C++17)
#include <optional>
#include <random>
#include <tuple>

using i64 = long long;

i64 gcd_(i64 a, i64 b) {
    a = std::llabs(a); b = std::llabs(b);
    while (b) { i64 t = a % b; a = b; b = t; }
    return a;
}

i64 lcm_(i64 a, i64 b) {
    if (a == 0 || b == 0) return 0;
    return std::llabs(a / gcd_(a, b) * b);           // divide first
}

// Iterative extended Euclid for a, b >= 0: returns (g, x, y) with a*x + b*y == g.
std::tuple<i64, i64, i64> ext_gcd(i64 a, i64 b) {
    i64 old_r = a, r = b, old_x = 1, x = 0, old_y = 0, y = 1;
    while (r) {
        i64 q = old_r / r, t;
        t = old_r - q * r; old_r = r; r = t;
        t = old_x - q * x; old_x = x; x = t;
        t = old_y - q * y; old_y = y; y = t;
    }
    return {old_r, old_x, old_y};
}

struct Dio { i64 x0, y0, dx, dy; };   // all solutions: (x0 + dx*t, y0 - dy*t)

std::optional<Dio> diophantine(i64 a, i64 b, i64 c) {
    if (a == 0 && b == 0) return c == 0 ? std::optional<Dio>(Dio{0, 0, 0, 0}) : std::nullopt;
    auto [g, x, y] = ext_gcd(std::llabs(a), std::llabs(b));
    if (c % g != 0) return std::nullopt;
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    // __int128 keeps the scaling exact; real code should check it fits back in 64 bits
    __int128 X = (__int128)x * (c / g), Y = (__int128)y * (c / g);
    return Dio{(i64)X, (i64)Y, b / g, a / g};
}

int euclid_steps(i64 a, i64 b) {
    int s = 0;
    while (b) { i64 t = a % b; a = b; b = t; ++s; }
    return s;
}

int main() {
    assert(gcd_(252, 105) == 21 && gcd_(12, 18) == 6 && gcd_(7, 0) == 7 && gcd_(-12, 18) == 6);
    assert(lcm_(12, 18) == 36 && lcm_(3000000000LL, 3000000000LL) == 3000000000LL);
    auto [g, x, y] = ext_gcd(240, 46);
    assert(g == 2 && x == -9 && y == 47);
    auto d = diophantine(240, 46, 6);
    assert(d && d->x0 == -27 && d->y0 == 141 && d->dx == 23 && d->dy == 120);
    assert(!diophantine(6, 10, 7));
    auto n = diophantine(-4, 6, 10);
    assert(n && -4 * n->x0 + 6 * n->y0 == 10);
    assert(euclid_steps(89, 55) == 9 && euclid_steps(144, 89) == 10);
    std::mt19937_64 rng(1);
    for (int i = 0; i < 2000; ++i) {
        i64 a = rng() % 1000000000000LL, b = rng() % 1000000000000LL;
        auto [gg, xx, yy] = ext_gcd(a, b);
        assert(gg == std::gcd(a, b));
        assert((__int128)a * xx + (__int128)b * yy == gg);
    }
    std::cout << "gcd tests passed\n";
}
// Numbers are exact up to 2^53 - 1; use the bigint versions for anything larger.
function gcd(a: number, b: number): number {
  a = Math.abs(a); b = Math.abs(b);
  while (b !== 0) { const t = a % b; a = b; b = t; }
  return a;
}

function lcm(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return Math.abs((a / gcd(a, b)) * b);          // divide first
}

function gcdBig(a: bigint, b: bigint): bigint {
  if (a < 0n) a = -a;
  if (b < 0n) b = -b;
  while (b !== 0n) { const t = a % b; a = b; b = t; }
  return a;
}

/** Extended Euclid for a, b >= 0 on bigint: [g, x, y] with a*x + b*y == g. */
function extGcd(a: bigint, b: bigint): [bigint, bigint, bigint] {
  let oldR = a, r = b, oldX = 1n, x = 0n, oldY = 0n, y = 1n;
  while (r !== 0n) {
    const q = oldR / r;                           // bigint division truncates; fine for r > 0
    [oldR, r] = [r, oldR - q * r];
    [oldX, x] = [x, oldX - q * x];
    [oldY, y] = [y, oldY - q * y];
  }
  return [oldR, oldX, oldY];
}

/** [x0, y0, dx, dy] with all solutions (x0 + dx*t, y0 - dy*t), or null. */
function diophantine(a: bigint, b: bigint, c: bigint): [bigint, bigint, bigint, bigint] | null {
  if (a === 0n && b === 0n) return c === 0n ? [0n, 0n, 0n, 0n] : null;
  const abs = (v: bigint) => (v < 0n ? -v : v);
  let [g, x, y] = extGcd(abs(a), abs(b));
  if (c % g !== 0n) return null;
  if (a < 0n) x = -x;
  if (b < 0n) y = -y;
  return [x * (c / g), y * (c / g), b / g, a / g];
}

function euclidSteps(a: number, b: number): number {
  let s = 0;
  while (b !== 0) { const t = a % b; a = b; b = t; s++; }
  return s;
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error("FAILED: " + msg);
}

check(gcd(252, 105) === 21 && gcd(12, 18) === 6 && gcd(7, 0) === 7 && gcd(-12, 18) === 6, "gcd");
check(lcm(12, 18) === 36 && lcm(3e9, 3e9) === 3e9, "lcm");
const [g, x, y] = extGcd(240n, 46n);
check(g === 2n && x === -9n && y === 47n, "extGcd");
const d = diophantine(240n, 46n, 6n);
check(d !== null && d[0] === -27n && d[1] === 141n && d[2] === 23n && d[3] === 120n, "dio");
check(diophantine(6n, 10n, 7n) === null, "dio none");
const n = diophantine(-4n, 6n, 10n)!;
check(-4n * n[0] + 6n * n[1] === 10n, "dio neg");
check(euclidSteps(89, 55) === 9 && euclidSteps(144, 89) === 10, "lame");
for (let i = 0; i < 2000; i++) {
  const a = BigInt(Math.floor(Math.random() * 1e12)), b = BigInt(Math.floor(Math.random() * 1e12));
  const [gg, xx, yy] = extGcd(a, b);
  check(gg === gcdBig(a, b) && a * xx + b * yy === gg, "random bezout");
}
console.log("gcd tests passed");

Sieves, smallest prime factors, factorization, divisors

from math import isqrt


def sieve(n: int) -> bytearray:
    """is_prime[k] for 0 <= k <= n (Eratosthenes, start at p*p, stop at sqrt n)."""
    is_prime = bytearray([1]) * (n + 1)
    is_prime[0:2] = b"\x00\x00"[: min(2, n + 1)]
    for p in range(2, isqrt(n) + 1):
        if is_prime[p]:
            is_prime[p * p :: p] = bytes(len(range(p * p, n + 1, p)))   # slice assignment = C speed
    return is_prime


def linear_sieve(n: int) -> tuple[list[int], list[int]]:
    """Smallest prime factor of every k <= n, and the list of primes. O(n)."""
    spf = [0] * (n + 1)
    primes: list[int] = []
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
        si = spf[i]
        for p in primes:
            if p > si or i * p > n:
                break
            spf[i * p] = p
    return spf, primes


def segmented_sieve(lo: int, hi: int) -> list[int]:
    """All primes in [lo, hi]. Memory O(sqrt(hi) + hi - lo)."""
    if hi < 2:
        return []
    lo = max(lo, 2)
    base = [p for p, f in enumerate(sieve(isqrt(hi))) if f]
    mark = bytearray([1]) * (hi - lo + 1)
    for p in base:
        start = max(p * p, (lo + p - 1) // p * p)
        mark[start - lo :: p] = bytes(len(range(start, hi + 1, p)))
    return [lo + i for i, f in enumerate(mark) if f]


def factorize(n: int) -> list[tuple[int, int]]:
    """Trial division, O(sqrt n). Returns [(prime, exponent), ...]."""
    out = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            e = 0
            while n % d == 0:
                n //= d
                e += 1
            out.append((d, e))
        d += 1 if d == 2 else 2          # 2, 3, 5, 7, 9, ...
    if n > 1:
        out.append((n, 1))
    return out


def factorize_spf(n: int, spf: list[int]) -> list[tuple[int, int]]:
    """O(log n) using a smallest-prime-factor table."""
    out = []
    while n > 1:
        p, e = spf[n], 0
        while n % p == 0:
            n //= p
            e += 1
        out.append((p, e))
    return out


def num_divisors(f):
    r = 1
    for _, e in f:
        r *= e + 1
    return r


def sum_divisors(f):
    r = 1
    for p, e in f:
        r *= (p ** (e + 1) - 1) // (p - 1)
    return r


if __name__ == "__main__":
    s = sieve(10**6)
    assert sum(s[:31]) == 10 and sum(s[:101]) == 25 and sum(s) == 78498
    spf, primes = linear_sieve(10**6)
    assert len(primes) == 78498 and primes == [k for k in range(10**6 + 1) if s[k]]
    assert spf[2:21] == [2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2]
    assert segmented_sieve(999_000, 10**6) == [k for k in range(999_000, 10**6 + 1) if s[k]]
    assert segmented_sieve(10**12, 10**12 + 100)[:2] == [10**12 + 39, 10**12 + 61]
    assert len(segmented_sieve(10**9, 10**9 + 1000)) == 49
    assert factorize(360) == [(2, 3), (3, 2), (5, 1)] == factorize_spf(360, spf)
    assert factorize(10**12 + 39) == [(10**12 + 39, 1)]
    assert num_divisors(factorize(360)) == 24 and sum_divisors(factorize(360)) == 1170
    assert num_divisors(factorize(720720)) == 240
    assert num_divisors(factorize(735134400)) == 1344
    for x in range(1, 3000):                      # brute-force cross-check
        divs = [d for d in range(1, x + 1) if x % d == 0]
        f = factorize(x)
        assert f == factorize_spf(x, spf)
        assert num_divisors(f) == len(divs) and sum_divisors(f) == sum(divs)
    print("sieve tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Sieves {
    static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        if (n >= 1) isPrime[1] = false;
        for (int p = 2; (long) p * p <= n; p++)
            if (isPrime[p])
                for (int m = p * p; m <= n; m += p) isPrime[m] = false;
        return isPrime;
    }

    static int[] spf;                              // filled by linearSieve
    static List<Integer> linearSieve(int n) {
        spf = new int[n + 1];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) { spf[i] = i; primes.add(i); }
            for (int p : primes) {
                if (p > spf[i] || (long) i * p > n) break;
                spf[i * p] = p;
            }
        }
        return primes;
    }

    static List<Long> segmentedSieve(long lo, long hi) {
        List<Long> out = new ArrayList<>();
        if (hi < 2) return out;
        lo = Math.max(lo, 2);
        int root = (int) Math.sqrt((double) hi);
        while ((long) (root + 1) * (root + 1) <= hi) root++;
        while ((long) root * root > hi) root--;
        boolean[] base = sieve(root);
        boolean[] mark = new boolean[(int) (hi - lo + 1)];
        Arrays.fill(mark, true);
        for (int p = 2; p <= root; p++) {
            if (!base[p]) continue;
            long start = Math.max((long) p * p, (lo + p - 1) / p * p);
            for (long m = start; m <= hi; m += p) mark[(int) (m - lo)] = false;
        }
        for (int i = 0; i < mark.length; i++) if (mark[i]) out.add(lo + i);
        return out;
    }

    /** Trial division: pairs {prime, exponent}. */
    static List<long[]> factorize(long n) {
        List<long[]> out = new ArrayList<>();
        for (long d = 2; d * d <= n; d += (d == 2 ? 1 : 2)) {
            if (n % d != 0) continue;
            int e = 0;
            while (n % d == 0) { n /= d; e++; }
            out.add(new long[]{d, e});
        }
        if (n > 1) out.add(new long[]{n, 1});
        return out;
    }

    static List<long[]> factorizeSpf(int n) {
        List<long[]> out = new ArrayList<>();
        while (n > 1) {
            int p = spf[n], e = 0;
            while (n % p == 0) { n /= p; e++; }
            out.add(new long[]{p, e});
        }
        return out;
    }

    static long numDivisors(List<long[]> f) {
        long r = 1;
        for (long[] pe : f) r *= pe[1] + 1;
        return r;
    }

    static long sumDivisors(List<long[]> f) {
        long r = 1;
        for (long[] pe : f) {
            long term = 1, pw = 1;
            for (int i = 0; i < pe[1]; i++) { pw *= pe[0]; term += pw; }   // 1 + p + ... + p^e
            r *= term;
        }
        return r;
    }

    static String show(List<long[]> f) {
        StringBuilder sb = new StringBuilder();
        for (long[] pe : f) sb.append(pe[0]).append('^').append(pe[1]).append(' ');
        return sb.toString().trim();
    }

    static void check(boolean c, String m) { if (!c) throw new AssertionError(m); }

    public static void main(String[] args) {
        boolean[] s = sieve(1_000_000);
        int count = 0;
        for (boolean b : s) if (b) count++;
        check(count == 78498, "pi(1e6)");
        List<Integer> primes = linearSieve(1_000_000);
        check(primes.size() == 78498, "linear sieve count");
        int[] want = {2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2};
        check(Arrays.equals(Arrays.copyOfRange(spf, 2, 21), want), "spf table");
        List<Long> seg = segmentedSieve(999_000, 1_000_000);
        int idx = 0;
        for (int k = 999_000; k <= 1_000_000; k++) if (s[k]) check(seg.get(idx++) == k, "segment");
        check(idx == seg.size(), "segment size");
        List<Long> big = segmentedSieve(1_000_000_000_000L, 1_000_000_000_100L);
        check(big.get(0) == 1_000_000_000_039L && big.get(1) == 1_000_000_000_061L, "1e12");
        check(segmentedSieve(1_000_000_000L, 1_000_001_000L).size() == 49, "49 primes");
        check(show(factorize(360)).equals("2^3 3^2 5^1") && show(factorizeSpf(360)).equals("2^3 3^2 5^1"), "360");
        check(numDivisors(factorize(360)) == 24 && sumDivisors(factorize(360)) == 1170, "d, sigma");
        check(numDivisors(factorize(735134400L)) == 1344, "1344");
        for (int x = 1; x < 3000; x++) {
            long cnt = 0, sum = 0;
            for (int d = 1; d <= x; d++) if (x % d == 0) { cnt++; sum += d; }
            check(numDivisors(factorize(x)) == cnt && sumDivisors(factorizeSpf(x)) == sum, "brute " + x);
        }
        System.out.println("sieve tests passed");
    }
}
#include <cassert>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

using i64 = long long;
using Factors = std::vector<std::pair<i64, int>>;

std::vector<char> sieve(int n) {
    std::vector<char> is_prime(n + 1, 1);
    is_prime[0] = 0;
    if (n >= 1) is_prime[1] = 0;
    for (int p = 2; (i64)p * p <= n; ++p)
        if (is_prime[p])
            for (int m = p * p; m <= n; m += p) is_prime[m] = 0;
    return is_prime;
}

// Smallest prime factor of every k <= n, plus the primes. O(n).
std::vector<int> linear_sieve(int n, std::vector<int>& primes) {
    std::vector<int> spf(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        if (spf[i] == 0) { spf[i] = i; primes.push_back(i); }
        for (int p : primes) {
            if (p > spf[i] || (i64)i * p > n) break;
            spf[i * p] = p;
        }
    }
    return spf;
}

i64 isqrt_(i64 n) {
    i64 r = (i64)std::sqrt((long double)n);
    while (r * r > n) --r;
    while ((r + 1) * (r + 1) <= n) ++r;
    return r;
}

std::vector<i64> segmented_sieve(i64 lo, i64 hi) {
    std::vector<i64> out;
    if (hi < 2) return out;
    lo = std::max(lo, 2LL);
    int root = (int)isqrt_(hi);
    std::vector<char> base = sieve(root), mark(hi - lo + 1, 1);
    for (int p = 2; p <= root; ++p) {
        if (!base[p]) continue;
        i64 start = std::max((i64)p * p, (lo + p - 1) / p * p);
        for (i64 m = start; m <= hi; m += p) mark[m - lo] = 0;
    }
    for (i64 i = 0; i < (i64)mark.size(); ++i) if (mark[i]) out.push_back(lo + i);
    return out;
}

Factors factorize(i64 n) {                       // trial division, O(sqrt n)
    Factors out;
    for (i64 d = 2; d * d <= n; d += (d == 2 ? 1 : 2)) {
        if (n % d) continue;
        int e = 0;
        while (n % d == 0) { n /= d; ++e; }
        out.push_back({d, e});
    }
    if (n > 1) out.push_back({n, 1});
    return out;
}

Factors factorize_spf(int n, const std::vector<int>& spf) {   // O(log n)
    Factors out;
    while (n > 1) {
        int p = spf[n], e = 0;
        while (n % p == 0) { n /= p; ++e; }
        out.push_back({p, e});
    }
    return out;
}

i64 num_divisors(const Factors& f) {
    i64 r = 1;
    for (auto& [p, e] : f) r *= e + 1;
    return r;
}

i64 sum_divisors(const Factors& f) {
    i64 r = 1;
    for (auto& [p, e] : f) {
        i64 term = 1, pw = 1;
        for (int i = 0; i < e; ++i) { pw *= p; term += pw; }
        r *= term;
    }
    return r;
}

int main() {
    auto s = sieve(1000000);
    int count = 0;
    for (char c : s) count += c;
    assert(count == 78498);
    std::vector<int> primes;
    auto spf = linear_sieve(1000000, primes);
    assert(primes.size() == 78498u);
    std::vector<int> want = {2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2};
    assert(std::vector<int>(spf.begin() + 2, spf.begin() + 21) == want);
    auto seg = segmented_sieve(999000, 1000000);
    std::vector<i64> ref;
    for (int k = 999000; k <= 1000000; ++k) if (s[k]) ref.push_back(k);
    assert(seg == ref);
    auto big = segmented_sieve(1000000000000LL, 1000000000100LL);
    assert(big[0] == 1000000000039LL && big[1] == 1000000000061LL);
    assert(segmented_sieve(1000000000LL, 1000001000LL).size() == 49u);
    Factors f360 = {{2, 3}, {3, 2}, {5, 1}};
    assert(factorize(360) == f360 && factorize_spf(360, spf) == f360);
    assert(num_divisors(f360) == 24 && sum_divisors(f360) == 1170);
    assert(num_divisors(factorize(897612484786617600LL)) == 103680);
    for (int x = 1; x < 3000; ++x) {
        i64 cnt = 0, sum = 0;
        for (int d = 1; d <= x; ++d) if (x % d == 0) { ++cnt; sum += d; }
        assert(num_divisors(factorize(x)) == cnt && sum_divisors(factorize_spf(x, spf)) == sum);
    }
    std::cout << "sieve tests passed\n";
}
function sieve(n: number): Uint8Array {
  const isPrime = new Uint8Array(n + 1).fill(1);
  isPrime[0] = 0;
  if (n >= 1) isPrime[1] = 0;
  for (let p = 2; p * p <= n; p++)
    if (isPrime[p]) for (let m = p * p; m <= n; m += p) isPrime[m] = 0;
  return isPrime;
}

/** Smallest prime factor table and prime list, O(n). */
function linearSieve(n: number): { spf: Int32Array; primes: number[] } {
  const spf = new Int32Array(n + 1);
  const primes: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (spf[i] === 0) { spf[i] = i; primes.push(i); }
    for (const p of primes) {
      if (p > spf[i] || i * p > n) break;
      spf[i * p] = p;
    }
  }
  return { spf, primes };
}

/** Primes in [lo, hi]; hi must stay below 2^53. */
function segmentedSieve(lo: number, hi: number): number[] {
  if (hi < 2) return [];
  lo = Math.max(lo, 2);
  let root = Math.floor(Math.sqrt(hi));
  while (root * root > hi) root--;
  while ((root + 1) * (root + 1) <= hi) root++;
  const base = sieve(root);
  const mark = new Uint8Array(hi - lo + 1).fill(1);
  for (let p = 2; p <= root; p++) {
    if (!base[p]) continue;
    const start = Math.max(p * p, Math.ceil(lo / p) * p);
    for (let m = start; m <= hi; m += p) mark[m - lo] = 0;
  }
  const out: number[] = [];
  for (let i = 0; i < mark.length; i++) if (mark[i]) out.push(lo + i);
  return out;
}

type Factors = Array<[number, number]>;

function factorize(n: number): Factors {
  const out: Factors = [];
  for (let d = 2; d * d <= n; d += d === 2 ? 1 : 2) {
    if (n % d !== 0) continue;
    let e = 0;
    while (n % d === 0) { n /= d; e++; }
    out.push([d, e]);
  }
  if (n > 1) out.push([n, 1]);
  return out;
}

function factorizeSpf(n: number, spf: Int32Array): Factors {
  const out: Factors = [];
  while (n > 1) {
    const p = spf[n];
    let e = 0;
    while (n % p === 0) { n /= p; e++; }
    out.push([p, e]);
  }
  return out;
}

const numDivisors = (f: Factors) => f.reduce((r, [, e]) => r * (e + 1), 1);
const sumDivisors = (f: Factors) =>
  f.reduce((r, [p, e]) => r * ((p ** (e + 1) - 1) / (p - 1)), 1);

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error("FAILED: " + msg);
}

const s = sieve(1_000_000);
check(s.reduce((a, b) => a + b, 0) === 78498, "pi(1e6)");
const { spf, primes } = linearSieve(1_000_000);
check(primes.length === 78498, "linear count");
check(Array.from(spf.slice(2, 21)).join(",") === "2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,17,2,19,2", "spf");
const ref: number[] = [];
for (let k = 999_000; k <= 1_000_000; k++) if (s[k]) ref.push(k);
check(segmentedSieve(999_000, 1_000_000).join() === ref.join(), "segment");
const big = segmentedSieve(1e12, 1e12 + 100);
check(big[0] === 1e12 + 39 && big[1] === 1e12 + 61, "1e12");
check(segmentedSieve(1e9, 1e9 + 1000).length === 49, "49 primes");
check(JSON.stringify(factorize(360)) === "[[2,3],[3,2],[5,1]]", "360");
check(JSON.stringify(factorizeSpf(360, spf)) === "[[2,3],[3,2],[5,1]]", "360 spf");
check(numDivisors(factorize(360)) === 24 && sumDivisors(factorize(360)) === 1170, "d sigma");
for (let x = 1; x < 3000; x++) {
  let cnt = 0, sum = 0;
  for (let d = 1; d <= x; d++) if (x % d === 0) { cnt++; sum += d; }
  check(numDivisors(factorize(x)) === cnt && sumDivisors(factorizeSpf(x, spf)) === sum, "brute " + x);
}
console.log("sieve tests passed");

Real-world uses

  • Rational arithmetic. Python's fractions.Fraction divides numerator and denominator by their GCD after every operation, so Fraction(6, 4) is stored as 3/2. Java's BigInteger.gcd, GMP's mpz_gcd and the C++17 std::gcd/std::lcm in <numeric> exist for exactly this. For very large integers, libraries use faster variants of Euclid: CPython's math.gcd uses Lehmer's algorithm for multi-word integers, and GMP switches to subquadratic "half-GCD" methods for numbers of thousands of words (GMP manual, "Greatest Common Divisor Algorithms").
  • RSA key generation. Pick primes , choose (usually 65537) with , and get the private exponent from extended Euclid as or . The classic worked example is in Modular Arithmetic, and the engineering side in Cryptography for Engineers.
  • Prime generation for keys. Generating a 1024-bit prime means testing random odd candidates. Libraries first trial-divide each candidate by a built-in table of small primes (OpenSSL's bn_prime.c carries one), which rejects most composites for almost nothing, and only then run the Miller–Rabin test. By the prime number theorem about 1 in numbers of that size is prime, so roughly 355 odd candidates are tried on average.
  • Hash-table sizes. libstdc++'s std::unordered_map grows its bucket array through a fixed list of primes, so that a hash function with a pattern (all keys multiples of 8, say) still spreads keys over every bucket. Java's HashMap instead uses powers of two and mixes the high bits of the hash into the low ones. See Hash Tables.
  • Periodic schedules. In real-time systems the hyperperiod of tasks with periods 10 ms, 25 ms and 40 ms is ms: a cyclic executive schedule only needs to be computed for that long and then repeats. Same with "when do these two cron jobs collide?"
  • Graphics and media. Aspect ratio from a resolution ( via ); Bresenham-style line drawing and rational resampling (audio resamplers convert 44.1 kHz to 48 kHz by the ratio , which is divided by their gcd 300).
  • Prime tables at scale. primesieve (Kim Walisch) generates primes with a segmented, wheel-optimised sieve of Eratosthenes and is used by mathematical software to count and enumerate primes up to and beyond; the Great Internet Mersenne Prime Search uses sieving and trial factoring to discard candidates before the expensive Lucas–Lehmer test.

Pitfalls & edge cases

  • gcd(0, 0). Mathematically undefined or 0 by convention; every standard library returns 0. Code that divides by the GCD (a / gcd(a, b)) must guard against it.
  • Negative inputs. gcd(-12, 18) should be 6. C++ std::gcd and Python math.gcd return non-negative results; a hand-written Euclid in C++/Java with negative inputs can return a negative number because % keeps the dividend's sign. Take absolute values first.
  • abs(LLONG_MIN) overflows in C++ and Java ( has no positive 64-bit counterpart). If inputs can be the minimum value, handle it or use unsigned arithmetic.
  • LCM overflow. a * b / gcd(a, b) overflows long before the LCM does. Always a / gcd(a, b) * b. And the LCM of many numbers grows very fast: , so "LCM of an array" needs a cap or big integers.
  • Recursion depth. Recursive Euclid is fine (depth ≤ ~92 for 64-bit), but recursive code elsewhere in a number-theory solution often is not.
  • Sieve upper bound off by one. Allocate n + 1 flags when itself must be tested. is_prime[1] must be false. When handle the tiny arrays.
  • i * p and p * p overflow in 32-bit loops near . Cast to 64-bit in the loop condition, as the code above does.
  • Sieve memory. A vector<int> SPF table for is 400 MB. Use a byte sieve, a bitset, odd-only storage, or a segmented sieve.
  • Floating-point square roots. (int)sqrt(n) can be off by one for near and above. Use an integer square root (math.isqrt) or correct the float result with two while loops, as the C++ and TypeScript code do.
  • Trial division leftovers. Forgetting the final if n > 1: record n drops the largest prime factor.
  • Diophantine scaling overflow. may exceed 64 bits; see the warning in the mechanics section.
  • Counting by looping to . Loop to and count pairs; a perfect square has one unpaired divisor.

Variations

  • Binary GCD (Stein's algorithm). Uses , for odd , and for odd . With a count-trailing-zeros instruction it is often faster than division-based Euclid on 64-bit integers. See Bit Manipulation.
  • GCD of many numbers / subarrays. GCD is associative and commutative, so a sparse table or segment tree answers range-GCD queries. Along any prefix the running GCD changes at most times, which bounds "count subarrays with GCD = k" to distinct values per right end.
  • Wheel factorization. Skip multiples of 2, 3, 5 (only 8 residues out of every 30 can be prime) in both trial division and sieving: a constant-factor speed-up of up to 3.75×.
  • Sieving multiplicative functions. The linear sieve computes Euler's totient , the Möbius function and the divisor count in the same pass, because for the value at depends only on the value at and on whether . Totients are in Modular Arithmetic; Möbius inversion is in Number Theory II.
  • Factorizing big numbers. For up to , trial division is too slow ( steps). Pollard's rho with Miller–Rabin factors such numbers in milliseconds; that is Number Theory II.
  • Counting primes without listing them. Meissel–Lehmer and related methods compute in well under a second, using the distinct values of from Number Theory II.
  • Gaussian integers and polynomials. Euclid works in any domain with a "division with a smaller remainder": polynomials over a field (polynomial GCD is how CRCs and Reed–Solomon decoders reason) and Gaussian integers .

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Find Greatest Common Divisor of Array (LeetCode 1979) — GCD of the minimum and maximum of an array. Warm-up for writing Euclid.

Hint

gcd(min(nums), max(nums)). One line.

2. Count Primes (LeetCode 204) — Count primes strictly below . The canonical sieve problem.

Solution

Sieve of Eratosthenes up to ; count unmarked numbers. Note "strictly less than ".

from math import isqrt


def count_primes(n: int) -> int:
    if n < 3:
        return 0
    s = bytearray([1]) * n          # indices 0..n-1
    s[0] = s[1] = 0
    for p in range(2, isqrt(n - 1) + 1):
        if s[p]:
            s[p * p :: p] = bytes(len(range(p * p, n, p)))
    return sum(s)


assert count_primes(10) == 4 and count_primes(0) == 0 and count_primes(2) == 0
assert count_primes(10**6 + 1) == 78498

3. Greatest Common Divisor of Strings (LeetCode 1071) — Longest string that "divides" both strings by repetition. Teaches that Euclid's structure works beyond numbers.

Hint

If s + t != t + s there is no answer. Otherwise the answer is the prefix of length gcd(len(s), len(t)).

4. T-primes (Codeforces 230B) — Decide, for up to numbers up to , whether each has exactly three divisors. Teaches reasoning with .

Solution

means , so for a prime . Check that is a perfect square (integer square root) and that is prime, using one sieve up to .

from math import isqrt


def t_primes(queries):
    LIM = 10**6
    s = bytearray([1]) * (LIM + 1)
    s[0] = s[1] = 0
    for p in range(2, isqrt(LIM) + 1):
        if s[p]:
            s[p * p :: p] = bytes(len(range(p * p, LIM + 1, p)))
    out = []
    for n in queries:
        r = isqrt(n)
        out.append("YES" if r * r == n and s[r] else "NO")
    return out


assert t_primes([4, 5, 6, 9, 1, 10**12]) == ["YES", "NO", "NO", "YES", "NO", "NO"]
assert t_primes([999966000289]) == ["YES"]          # 999983^2, 999983 is prime

5. Water and Jug Problem (LeetCode 365) — Can two jugs measure exactly a target amount? Bézout's identity in disguise.

Hint

Possible iff target ≤ x + y and target is a multiple of gcd(x, y) (treat target 0 as possible).

6. Almost Prime (Codeforces 26A) — Count numbers up to 3000 with exactly two distinct prime divisors. Teaches the "count distinct prime factors" sieve.

Hint

For each prime , add 1 to every multiple of . Then count entries equal to 2.

7. Counting Divisors (CSES 1713) — for numbers up to . Teaches SPF factorization or a divisor sieve.

Solution

Build the SPF table once with the linear sieve, then each query factorizes in and multiplies .

def divisor_counts(queries, lim=10**6):
    spf = list(range(lim + 1))
    for p in range(2, int(lim**0.5) + 1):
        if spf[p] == p:
            for m in range(p * p, lim + 1, p):
                if spf[m] == m:
                    spf[m] = p
    out = []
    for x in queries:
        r = 1
        while x > 1:
            p, e = spf[x], 0
            while x % p == 0:
                x //= p
                e += 1
            r *= e + 1
        out.append(r)
    return out


assert divisor_counts([16, 17, 18, 720720], lim=10**6) == [5, 2, 6, 240]

(This version fills the SPF table with an Eratosthenes-style sieve that only writes unset entries; it gives the same table as the linear sieve.)

8. Closest Prime Numbers in Range (LeetCode 2523) — The pair of consecutive primes in with the smallest gap. Sieve then scan.

Hint

Sieve up to , walk the primes in in order, keep the smallest adjacent difference. Early exit when the gap is 2 (twin primes) — nothing beats it except (2, 3).

9. Common Divisors (CSES 1081) — Largest GCD of any pair from an array of values up to . Teaches iterating over the answer instead of the pairs.

Solution

Count occurrences of each value. For from down to 1, count how many array elements are multiples of (sum cnt[d], cnt[2d], ...). The first with count is the answer. Total work .

def max_pair_gcd(a):
    V = max(a)
    cnt = [0] * (V + 1)
    for x in a:
        cnt[x] += 1
    for d in range(V, 0, -1):
        if sum(cnt[d::d]) >= 2:
            return d
    return 0


assert max_pair_gcd([3, 14, 15, 7, 9]) == 7
assert max_pair_gcd([12, 18, 5]) == 6

10. Sum of Divisors (CSES 1082) — for . Teaches the "for each divisor , it contributes " swap and grouping equal quotients ( blocks).

Hint

. The value takes only distinct values; for each block of with the same quotient, add the arithmetic-series sum of those .

11. Line (Codeforces 7C) — Find any integer point on the line . A direct linear Diophantine equation.

Hint

Solve with extended Euclid. No solution iff . Watch signs of and .

12. Coprime (AtCoder ABC 177 E) — Decide whether an array is pairwise coprime, only setwise coprime, or neither. Teaches "no prime is shared" via SPF factorization.

Hint

Factorize each element with an SPF table; if any prime appears in two elements, it is not pairwise coprime. Setwise: GCD of all is 1.

13. Ugly Number III (LeetCode 1201) — The -th positive integer divisible by , or . Binary search on the answer + inclusion–exclusion with LCMs.

Hint

Count of numbers divisible by , or is . Binary search the smallest with count . Divide before multiplying in the LCMs.

14. Largest Component Size by Common Factor (LeetCode 952) — Connect numbers sharing a factor ; largest connected group. SPF + Union-Find.

Hint

Union each number with each of its prime factors (as extra nodes). Factorize with SPF. Count component sizes over the original numbers only.

Common mistakes & interview follow-ups

"Why is Euclid's algorithm correct?" State and prove : the two pairs have the same set of common divisors. Interviewers want the "same set" argument, not "because it works".

"What is its complexity, and what is the worst case?" . Worst case consecutive Fibonacci numbers (Lamé). Mention the halving-every-two-steps argument as the quick proof.

"Compute LCM of an array of 10^5 numbers." Fold lcm left to right, dividing before multiplying; point out that the result overflows quickly and ask whether a modulus or a cap is intended. If modulo is wanted, you cannot fold lcm mod (division by GCD does not commute with mod); take the max exponent of each prime over all factorizations instead.

"Why start the sieve at ?" Smaller multiples () have a smaller prime factor and are already crossed out.

"Is the sieve or ?" over primes is (Mertens). Summing over all would be , which is the divisor sieve, not Eratosthenes.

"Factor numbers up to ." Trial division is — too slow per number. Say Pollard's rho + Miller–Rabin, expected about steps.

"Do you need the linear sieve?" Only for the SPF table or multiplicative functions; for counting primes, an Eratosthenes sieve with bit packing is simpler and as fast.

Mistakes interviewers watch for: a * b / gcd; marking from (correct but slower) or from without 64-bit math; while (d * d <= n) with 32-bit d * d; forgetting the leftover prime; treating 1 as prime; negative modulo in hand-written GCD.

Quick quiz

1. How many steps does Euclid take on , and why is this pair special?

Answer

10 steps. They are consecutive Fibonacci numbers (), the worst case for their size: every quotient is 1.

2. Does have integer solutions? What about ?

Answer

. 7 does not divide 5, so no. 7 divides 35, so yes: one solution is ; all are .

3. In the sieve for , which primes actually cross anything out?

Answer

2, 3, 5, 7 — the primes .

4. How many divisors does have, and what is their sum?

Answer

. .

5. In the linear sieve, which pair marks 45?

Answer

, so , . At () the loop tries (marks 30) and (marks 45), then stops because the next prime 5 > 3.

6. Why is lcm of computed as a * b / gcd(a, b) wrong in Java's long?

Answer

is close to — here it just fits, but gives , which silently wraps. The correct LCM ( itself) needs no big intermediate if you divide first.

Further reading / sources

  • Donald E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. — §4.5.2 (Euclid, binary GCD) and §4.5.3 (analysis of Euclid's algorithm, Lamé's theorem).
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 31, "Number-Theoretic Algorithms" (§31.1–31.2: divisibility, GCD, extended Euclid).
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed. — Chapters 1–2 (fundamental theorem, primes), §22 (Mertens' theorems).
  • David Gries and Jayadev Misra, "A Linear Sieve Algorithm for Finding Prime Numbers", Communications of the ACM 21(12), 1978.
  • Josef Stein, "Computational problems associated with Racah algebra", Journal of Computational Physics 1(3), 1967 (binary GCD).
  • cp-algorithms: Euclidean algorithm, Extended Euclidean algorithm, Linear Diophantine equations, Sieve of Eratosthenes, Linear sieve, Integer factorization.
  • OEIS A006880 (number of primes below ) and A066150 (maximal number of divisors of any ).
  • Kim Walisch, primesieve — documentation of a production segmented sieve.

Lessons: previous — Module 8 overview · next — Modular Arithmetic · module — Math for Algorithms · course — DSA: Zero to Mastery.

Related Archon pages: Bit Manipulation · Randomized Algorithms (Miller–Rabin) · Hash Tables · Counting DP · Union-Find · Cryptography for Engineers · System Design Math.