• Support PF! Buy your school textbooks, materials and every day products Here!

Finding number of factorizations

  • Thread starter PhDorBust
  • Start date
  • #1
143
0
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
 

Answers and Replies

  • #2
33,262
4,963
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.
 
  • #3
143
0
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.
 

Related Threads on Finding number of factorizations

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
13
Views
2K
Replies
11
Views
2K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
3
Views
843
Top