Greatest Prime Factor


For an integer n>=2, let gpf(x) denote the greatest prime factor of n, i.e., the number p_k in the factorization


with p_i<p_j for i<j. For n=2, 3, ..., the first few are 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5, ... (OEIS A006530). The greatest multiple prime factors for squareful integers are 2, 2, 3, 2, 2, 3, 2, 2, 5, 3, 2, 2, 3, ... (OEIS A046028).


A number for which gpf(n)>sqrt(n) is called an unusual number by Greene and Knuth (1990) and a sqrt(n)-rough numbers by Finch (2001). The first few sqrt(n)-rough numbers are 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, ... (OEIS A064052). The probability that a random positive integer is sqrt(n)-rough is ln2 (Schroeppel 1972).

A number that is not sqrt(n)-rough is called, not surprisingly, a sqrt(n)-smooth number (or sometimes, a "round number"). The first few are 1, 4, 8, 9, 12, 16, 18, 24, 25, 27, ... (OEIS A048098).

See also

Dickman Function, Distinct Prime Factors, Factor, Golomb-Dickman Constant, Least Common Multiple, Least Prime Factor, Mangoldt Function, Prime Factor, Prime Factorization, Prime Number, Rough Number, Semiprime, Størmer Number, Twin Peaks

Explore with Wolfram|Alpha


Erdős, P. and Pomerance, C. "On the Largest Prime Factors of n and n+1." Aequationes Math. 17, 211-321, 1978.Finch, S. "RE: Unusual Numbers." 27 Aug 2001., D. H. and Knuth, D. E. Mathematics for the Analysis of Algorithms, 3rd ed. Boston, MA: Birkhäuser, 1990.Guy, R. K. "The Largest Prime Factor of n." §B46 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 101, 1994.Heath-Brown, D. R. "The Largest Prime Factor of the Integers in an Interval." Sci. China Ser. A 39, 449-476, 1996.Mahler, K. "On the Greatest Prime Factor of ax^m+by^n." Nieuw Arch. Wisk. 1, 113-122, 1953.Schroeppel, R. Item 29 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 13, Feb. 1972., N. J. A. Sequences A006530/M0428, A048098, and A064052 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Greatest Prime Factor

Cite this as:

Weisstein, Eric W. "Greatest Prime Factor." From MathWorld--A Wolfram Web Resource.

Subject classifications