Least Prime Factor


Let n>1 be any integer and let lpf(n) (also denoted LD(n)) be the least integer greater than 1 that divides n, i.e., the number p_1 in the factorization


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 composite then [lpf(n)]^2<=n (Séroul 2000, p. 7), with equality for n the square of 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 (x,y) such that

1. x<y,

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

3. For all z, x<z<y implies lpf(z)<lpf(x).

The least multiple prime factors for squareful integers 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. They also conjecture that

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

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, Twin Peaks

Explore with Wolfram|Alpha


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.Séroul, R. "The Lowest Divisor Function." §8.4 in Programming for Mathematicians. Berlin: 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 Web Resource.

Subject classifications