TOPICS
Search

Least Prime Factor


LeastPrimeFactor

The least prime factor lpf(n) (also denoted LD(n)) of an integer n>1 is the least integer greater than 1 that divides n, i.e., the number p_1 in the prime factorization

 n=p_1^(a_1)...p_k^(a_k),

with p_i<p_j for i<j. The least prime factor is implemented in the Wolfram Language as FactorInteger[n][[1,1]].

For n=2, 3, ..., the first few are 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, ... (OEIS A020639).

If n is a composite number then [lpf(n)]^2<=n (Séroul 2000, p. 7), with equality iff n=p^2 for a prime p.

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 (x,y) with 1<x<y such that

1. lpf(x)=lpf(y),

2. For every integer z, x<z<y implies lpf(z)<lpf(x).

For a squareful integer n, the least multiple prime factor is the smallest prime p with p^2 dividing n. This may differ from lpf(n), as it does for n=18. 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 N and k with 2<=k<=N/2, they conjecture that

 lpf(N; k)<=max(N/k,29).

Rudich and Rousseau (2026) reported a deterministic algorithm computing lpf(n) in n^(o(1)) steps, equivalently 2^(o(b)) steps for an input of b bits. Here o denotes little-o notation. Their formal statement uses the same Turing machine for every positive integer k, with a constant C_k bounding its time by C_k2^(b/k) on all b-bit inputs n>1. 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.


See also

Alladi-Grinstead Constant, Distinct Prime Factors, Erdős-Selfridge Function, Euclid-Mullin Sequence, Exceptional Binomial Coefficient, Factor, Good Binomial Coefficient, Greatest Prime Factor, Least Common Multiple, Mangoldt Function, Prime Factor, Prime Factorization Algorithms, Twin Peaks

Explore with Wolfram|Alpha

References

Erdős, P.; Lacampagne, C. B.; and Selfridge, J. L. "Estimates of the Least Prime Factor of a Binomial Coefficient." Math. Comput. 61, 215-224, 1993. https://doi.org/10.1090/S0025-5718-1993-1199990-6.Rudich, I. and Rousseau, L.-M. "Deterministic Factoring in Time N^(o(1))." Oct. 29, 2026. https://hexagonmath.org/2610.00600v1.Séroul, R. "The Lowest Divisor Function." §8.4 in Programming for Mathematicians. Berlin, Germany: Springer-Verlag, pp. 9-11 and 165-167, 2000.Sloane, N. J. A. Sequences A020639 and A046027 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Least Prime Factor

Cite this as:

Weisstein, Eric W. "Least Prime Factor." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LeastPrimeFactor.html

Subject classifications