Find all divisors of for example 29601

  • #1
symplectic_manifold
60
0
A question:
If I want to find all divisors of for example 29601 and in general all divisors of any (large) number, do I have to do it "on foot" i.e. with help of the division rules or checking each number looking if it divides the given number?...As far as I know there is no unified algorithm for computing the divisors of any number...or am I wrong? Does there exist such an algorithm? Computing divisors of small numbers is clearly a cheap task but I find it extremely tedious for large numbers.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
43,021
971
There exist algorithms (though still "tedious") for factoring numbers. Finding all divisors would then be a matter of partitioning the set of all prime factors. (But every partition gives you two divisors!)
 
  • #3
symplectic_manifold
60
0
"...An ordered factorization of the positive integer n into exactly l factors is an l-tuple (d_1, . . . , d_l) such that n = d_1 · · · d_l. The divisor function d(n)
counts the number of ordered factorizations of n into exactly two factors,
since each factorization n = dd' is completely determined by the first factor
d. For every positive integer l, we define the arithmetic function d_l(n)
the number of factorizations of n into exactly l factors. Then d_1(n) = 1
and d_2(n) = d(n) for all n..."

did you mean this?...I could barely understand anything however...it has something to do with multiplicative functions...it says.

Could you tell please me more about the term "partitioning of the set of prime numbers" and why every partition gives us two divisors? :smile:
 
  • #4
shmoe
Science Advisor
Homework Helper
1,994
1
Find prime factorization, e.g. [tex]60=2^{2}3^{1}5^{1}[/tex]. Any divisor will be of the form [tex]3=2^a3^b5^c[/tex] where 0<=a<=2, 0<=b<=1, 0<=c<=1, e.g [tex]2^03^15^0[/tex]. This corresponds to another divisor, [tex]60/3=20=2^23^05^1[/tex], and if you like you can think of this as a partition of the primes {2,2,3,5} into two 'multi'sets {3}, and {2,2,5}.

wherever that passage you quoted came from, it looks like they talk about the plain old divisor function d(n) earlier. Have a look at that section if possible.
 

Suggested for: Find all divisors of for example 29601

Replies
2
Views
614
  • Last Post
Replies
1
Views
690
Replies
55
Views
2K
Replies
8
Views
635
  • Last Post
Replies
6
Views
612
  • Last Post
Replies
2
Views
713
Replies
1
Views
2K
  • Last Post
Replies
1
Views
533
Replies
8
Views
573
Replies
5
Views
413
Top