1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Finding number of factorizations

  1. Oct 30, 2011 #1
    Given a number n, what would be the computationally most efficient procedure to find the number of unique factorizations.

    e.g. 24 has 4 factorizations
    24 = 1 * 24
    = 2 * 12
    = 3 * 8
    = 4 * 6
  2. jcsd
  3. Oct 30, 2011 #2


    Staff: Mentor

    For a given number n, determine whether the numbers in the set {2, 3, 4, ..., m} are divisors, where m <= √n. You don't need to check for 1 being a divisor.

    You can tweak the process some: if n is odd, then it won't be divisible by any even number.
  4. Nov 1, 2011 #3
    Yes, that is how I first approached it, but I suspect there is a better way.

    These are my thoughts. To find the number of factorizations of a number, find its prime factorization, then I *believe* there is some expression for the number of factors given this prime factorization.

    For example, given a number p^n, it will have n + 1 unique factorizations. I've written out the cases for (p1^n) * (p2 ^ m), where p,p1,p2 are arbitrary primes; but I am not getting the pattern for arbitrary (p1 ^ r1) ... (pn ^ rn) factorizations.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook