The least prime factor (also denoted
) of an integer
is the least integer
greater than 1 that divides
, i.e., the number
in the prime factorization
with
for
. The least prime factor is implemented in the
Wolfram Language as FactorInteger[n][[1,1]].
For , 3, ..., the first few are 2, 3, 2, 5, 2, 7, 2, 3,
2, 11, 2, 13, 2, 3, ... (OEIS A020639).
If
is a composite number then
(Séroul 2000, p. 7), with equality
iff
for a prime
.
A plot of the least prime factor function resembles a jagged terrain of mountains, which leads to the appellation of "twin peaks"
to a pair of integers with
such that
1. ,
2. For every integer ,
implies
.
For a squareful integer , the least multiple prime
factor is the smallest prime
with
dividing
. This may differ from
, as it does for
. The first values are 2, 2, 3, 2, 2, 3, 2, 2, 5,
3, 2, 2, 2, ... (OEIS A046027).
Erdős et al. (1993) consider the least prime factor of the binomial coefficients, and define what they term good
binomial coefficients and exceptional
binomial coefficients. For integers and
with
, they conjecture
that
Rudich and Rousseau (2026) reported a deterministic algorithm computing
in
steps, equivalently
steps for an input of
bits. Here
denotes little-o notation.
Their formal statement uses the same Turing machine
for every positive integer
, with a constant
bounding its time by
on all
-bit inputs
. The claimed bound would
also give complete prime factorization by
repeated calls, but that step was not formalized.
The construction re-proves the counting method used in the reported refutation of the exponential time hypothesis. Claude Opus 5.5 generated the ideas and Lean proof. The authors audited the formal statement but did not read the proof. They reported successful Lean checking with only its three standard axioms. As of Oct. 31, 2026, independent specialist verification of the complete claim had not been reported.