Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find all divisors of for example 29601

  1. Sep 16, 2005 #1
    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.
  2. jcsd
  3. Sep 16, 2005 #2


    User Avatar
    Science Advisor

    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!)
  4. Sep 16, 2005 #3
    "...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:
  5. Sep 16, 2005 #4


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook