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

    PhDorBust

    User Avatar

    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
     
    PhDorBust, Oct 30, 2011
  2. jcsd
    Phys.org - latest science and technology news stories on Phys.org
  3. Oct 30, 2011 #2

    Mark44

    User Avatar
    Insights Author

    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.
     
    Mark44, Oct 30, 2011
  4. Nov 1, 2011 #3

    PhDorBust

    User Avatar

    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.
     
    PhDorBust, Nov 1, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook