1. Not finding help here? Sign up for a free 30min 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!

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

    Mark44

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding number of factorizations
  1. Factoring a number (Replies: 1)

Loading...