Finding number of factorizations

PhDorBust · Oct 30, 2011

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

Mark44 · Oct 30, 2011

PhDorBust said: ↑

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

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.

PhDorBust · Nov 1, 2011

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.

Log in or Sign up

Finding number of factorizations

PhDorBust

Mark44

Staff: Mentor

PhDorBust

Factoring a number (Replies: 1)

Number theory factorization proof (Replies: 4)

Complex Numbers ~ Factors (Replies: 2)

[number theory] find number in certain domain with two prime factorizations (Replies: 3)

Factoring over real numbers (Replies: 1)