Number of Factors of an Integer

Given an integer N, there is a simple way to find the total number of its factors. The main tool for the feat is the prime number decomposition theorem.

Every integer N is the product of powers of prime numbers:

N = pαqβ· ... · rγ.

Where, p, q, ..., r are prime, while α, β, ..., γ are positive integers. Such representation is unique up to the order of the prime factors.

If N is a power of a prime, N = pα, then it has α + 1 factors:

1, p, ..., pα-1, pα.

Every prime in the prime number decomposition of N makes a similar contribution. Such contributions are independent of each other; according to the Product Rule of counting the total number of combinations - each a factor of N - equals

(α + 1)(β + 1) ... (γ + 1)

This formula helps answer such simple questions as, for example,

  1. What is the smallest positive integer that has 10 factors?
  2. What is the smallest positive integer that has 9 factors?
  3. What is the smallest positive integer that has 48 factors?
  4. What is the smallest positive integer that has more than 100 factors?

To answer the first question observe that 10 = 2·5, meaning that the number in question has just two prime factors in its decomposition - one with the exponent of α = 1, the other of β = 4: N = p1q4. To make N as small as possible, we have to choose the smallest available primes, 2 and 3. The answer is obviously N = 3124 = 48.

To answer the second question by the same token, observe that 9 = 3×3, implying again that the prime factorization of the number at hand includes only two prime factors, N = 2232 = 36.

For the third problem, my original thinking was to proceed as before: 48 = 2431 = 16×3, from which it appears α = 15 and β = 2. N = 21532. Wayne Gabrielson in a comment below found an error in this thinking. Having 15 different factors does not obligate them all to be multiples of a single prime number, like 215. The exponent grows too fast. We may as well interpret 16 as the product

(α + 1)(β + 1) ... (γ + 1)

where each α, β, ..., γ is 1 or, some are, say, 3. Making this choice we arrive at the answer to #3:

2 · 2 · 3 · 5 · 7 · 11 = 4620

that also has 48 factors but is much smaller than 21532 = 294912.

An indication that the problem is not as simple as it first appeared to be came on 17 November, 2014 when an anonymous visitor left a comment with 2520 = 2332·5·7 and 48 = (3+1)(2+1)(1+1)(1+1). A year and a half later T. D. Noe reminded me of that result in a private correspondence, with an extra claim (verified in Matematica) that the least number with 100 factors is 45360 which answers the fourth question.


Related material
Read more...

  • Factoring with the Factor Tree
  • GCD and LCM via Factor Tree
  • GCD and LCM by Plain Factorization
  • Common Multiples and the Least Common Multiple
  • GCD(M, N) x LCM(M, N) = M x N
  • Divisibility Criteria
  • Euclid's Algorithm
  • Algorithm for Computing the LCM
  • Factors And Multiples
  • Two Properties of Greatest Common Divisor
  • Properties of GCD and LCM
  • A Line in a Square Grid
  • Extension of Euclid's Game
  • |Contact| |Front page| |Contents| |Arithmetic|

    Copyright © 1996-2018 Alexander Bogomolny

    71471480