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

    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