Trial division

Trial division is the oldest factoring method there is: to learn about n, divide it by 2, 3, 4, … and see what goes in evenly. It is also the slowest — and it keeps appearing below anyway, because it is the only elementary method that answers the question most of these problems actually ask. A sieve tells you which numbers are prime. Miller–Rabin tells you whether one number is prime. Trial division tells you what a number is made of, and hands you the factors while it works.

Two jobs, one loop

The same loop does double duty, and it is worth being clear about which one you are running.

As a primality test, the loop is a search for a counterexample: if no d in 2 … √n divides n, nothing above √n can either (a divisor d > √n would force a cofactor n/d < √n, which the loop already ruled out), so n is prime. Cost is O(√n) divisions.

As a factorisation, the loop peels: when d divides, strip every copy of it before moving on. This is the version that carries most of the problems below, and it has a property that is easy to miss — because factors come out in increasing order and each is fully removed, every divisor the loop finds is automatically prime. No primality test is needed anywhere in a trial-division factoriser. The canonical shape, from solutions/public/p0012/:

d = 2
while d * d <= n:
    if n % d == 0:
        exp = 0
        while n % d == 0:
            n //= d
            exp += 1
        factors.append((d, exp))
    d += 1
if n > 1:
    factors.append((n, 1))

That trailing if n > 1 is the part people drop. When the loop ends, whatever is left is either 1 or a single prime larger than √n — the largest prime factor, unfindable by the loop itself because there is no room below the ceiling for its cofactor. Omitting it is the classic trial-division bug: correct for 12, silently wrong for 14.

The cuts that make it usable

Naive trial division is O(n); a few observations bring it to something practical.

Stop at √n. The single biggest win, and it is where the O(√n) comes from.
Shrink the ceiling as you go. After dividing out a factor the remainder is smaller, so the ceiling should come down with it. solutions/public/p0003/ recomputes it on every hit, which is what turns a 12-digit input into a few thousand divisions rather than a million:
```
if remaining_number % current_factor == 0:
    remaining_number = reduce(remaining_number, current_factor)
    search_limit = int(remaining_number ** 0.5)
```
Skip what cannot divide. Handle 2 separately, then step by 2 through the odds — half the work for one special case. A wheel goes further: after 2 and 3, every prime is 6k ± 1, so stepping d += 2, 4, 2, 4, … covers the candidates in a third of the iterations. Problem 118 uses exactly that wheel, because it tests a great many nine-digit permutations and the constant factor is the whole budget.
Divide by primes, not by integers. If you already have a prime list up to √n — which a sieve gives you cheaply — trial-dividing against it costs O(π(√n)) rather than O(√n), a further ln factor. solutions/public/p0029/ carries both versions for contrast, and problems 157, 176 and 234 all sieve first specifically to feed the divider.

The asymptotics hide an important asymmetry: O(√n) is the worst case, and it is reached only when n is prime or a semiprime with two large factors. On a smooth number the loop exits almost immediately. Trial division is cheap exactly when the number has small factors and expensive exactly when it does not — which is why it survives inside otherwise sophisticated solutions whenever the numbers being factored are known to be small or smooth. Problem 248 factorises 13! this way without apology; problems 545 and 932 use it for a target and a step and nothing else. Problem 359 is the extreme case. Its input is around 7·10¹³, so the worst-case bound is over eight million divisions, but the number is 2²⁷ · 3¹². Once the 2s and 3s are peeled off the remainder is 1, the d * d <= n test fails at d = 5, and the whole factorisation takes a few dozen divisions.

What you get beyond the verdict

Once you have the exponent vector n = p₁^e₁ · p₂^e₂ · …, the multiplicative functions fall out arithmetically, and this is usually the real reason a solution factors at all:

Wanted	From the factorisation
divisor count `τ(n)`	`∏ (eᵢ + 1)`
divisor sum `σ(n)`	`∏ (pᵢ^(eᵢ+1) − 1) / (pᵢ − 1)`
Euler's totient `φ(n)`	`n · ∏ (1 − 1/pᵢ)`
radical `rad(n)`	`∏ pᵢ`

Problems 12, 108, 157 and 926 all want τ; 188 and 243 want φ; each computes it by trial-dividing and then multiplying out. The pattern to internalise is that "count the divisors of n" is never a divisor-counting loop — it is a factorisation followed by a product over exponents.

A near relation worth naming separately is divisor pairing: the same d ≤ √n sweep, but instead of dividing out, you record both d and n/d on each hit. That enumerates all divisors (not just the prime ones) in O(√n), which is what solutions/public/p0021/ uses for its proper-divisor sums. Same ceiling, same loop, different payload — reach for pairing when you want the divisor list, for peeling when you want the prime structure.

The two combine, too. If you peel first, you can build the full divisor list from the exponent vector: start from [1], and for each pᵉ you strip, multiply every divisor so far by 1, p, …, pᵉ. Problem 251 does exactly this, dividing only by sieved primes, and problem 359 does it to list the 364 floor/room splits of its smooth input, where pairing would have swept millions of candidates to find them. Pairing always costs √n steps, even when n is smooth. Peel-and-expand costs the factorisation plus τ(n) multiplications, and against a prime list the factorisation stops as soon as p² > remainder. When you need the divisors of many unrelated large numbers, that difference is the budget.

When to reach for something else

Trial division is the default until one of three things is true.

You need the factorisations of a whole range. Then O(√n) per number becomes O(n√n) overall, and a smallest-prime-factor sieve replaces it with one O(n log log n) build plus O(log n) lookups per number. Problems 130 and 545 both do this. The contrast is on display in solutions/public/p0010/, which solves the same problem four ways: the trial-division version is O(n√n / log n) and is there precisely to show what the sieve buys. The condition is a whole range, though, not just many numbers. Problem 251 factorises one number per step of a walk whose values are spaced far apart and reach into the tens of millions. A smallest-prime-factor table over that span would mostly cover numbers it never reads. So the solution sieves only to the square root and trial-divides each visited number against that prime list. It caps the number of visits by placing a crossover at L^(1/4), past which a different walk takes over. Trial division is the per-item cost that crossover is tuned against.
You only need the verdict, and n is large. √10¹⁸ is a billion divisions; Miller–Rabin settles the same number in a handful of modular exponentiations. Problems 131, 248, 293 and 545 all pair a small-prime trial-division prefilter with Miller–Rabin behind it — the two are complements, not rivals. A dozen cheap n % p checks strip out most composites before any expensive test runs.
You need the factors of a large number. Trial division cannot reach a 60-bit semiprime. That is Pollard's rho territory, or a proper sieve method. Even there trial division keeps a job, as a front end with a fixed bound rather than √n. Problem 271 divides by every d below 1000, and only then passes whatever cofactor is left to Miller–Rabin and Pollard's rho. Rho has a hard time with tiny factors and repeated factors. A thousand cheap divisions remove both, so rho only ever sees a cofactor whose prime factors are all large. Capping the loop also means its cost no longer depends on n. The main input there is a primorial, so the front end factors it completely and rho never runs. The harder test case, 63 times two nine-digit primes, is the one that reaches rho.

Details that bite

Prefer d * d <= n to d <= int(n ** 0.5). The comparison stays in exact integer arithmetic. Float sqrt is fine up to about 2⁵³, but beyond that the rounding can put the ceiling one short and drop a factor — a bug that shows up only on the large inputs you were least likely to test.
Order the guards by cost. n < 2 and the even case before the loop, then odds only. Every branch you take before entering the loop is free relative to the loop.
Watch the loop condition after you divide. If you shrink n inside the body, the while d * d <= n test re-reads the new n — which is the behaviour you want, but it means the loop bound is not what a reader assumes from the first line. Say so in a comment when it matters.
Build prime lists inside solve(). A sieve used to feed the divider belongs in the function, sized to the input. With --runs=N the harness times repeated solve() calls, so a list built once at module import is free from the second run onward and the benchmark understates the real cost.

Problems44 / 44

● 0003 — Largest Prime Factor
● 0010 — Summation of Primes
● 0012 — Highly Divisible Triangular Number
● 0021 — Amicable Numbers
● 0023 — Non-Abundant Sums
● 0027 — Quadratic Primes
● 0029 — Distinct Powers
● 0041 — Pandigital Prime
● 0046 — Goldbach's Other Conjecture
● 0047 — Distinct Primes Factors
● 0051 — Prime Digit Replacements
● 0058 — Spiral Primes
● 0060 — Prime Pair Sets
● 0069 — Totient Maximum
● 0108 — Diophantine Reciprocals I
● 0118 — Pandigital Prime Sets
● 0128 — Hexagonal Tile Differences
● 0130 — Composites with Prime Repunit Property
● 0131 — Prime Cube Partnership
● 0132 — Large Repunit Factors
● 0152 — Sums of Square Reciprocals
● 0157 — Base-10 Diophantine Reciprocal
● 0170 — Pandigital Concatenating Products
● 0176 — Common Cathetus Right-angled Triangles
● 0188 — Hyperexponentiation
● 0202 — Laserbeam
● 0221 — Alexandrian Integers
● 0234 — Semidivisible Numbers
● 0243 — Resilience
● 0248 — Euler's Totient Function Equals 13!
● 0251 — Cardano Triplets
● 0271 — Modular Cubes, Part 1
● 0293 — Pseudo-Fortunate Numbers
● 0357 — Prime Generating Integers
● 0359 — Hilbert's New Hotel
● 0437 — Fibonacci Primitive Roots
● 0478 — Mixtures
● 0545 — Faulhaber's Formulas
● 0581 — $47$-smooth Triangular Numbers
● 0605 — Pairwise Coin-Tossing Game
● 0694 — Cube-full Divisors
● 0853 — Pisano Periods 1
● 0926 — Total Roundness
● 0932 — $2025$