Re: ISO algorithm to list all divisors of a number

On Sun, 28 Aug 2005 02:19:45 +0000 (UTC), kj <socyl@xxxxxxxxxxxxxxxxx>
wrote:

>
>
>Hi! I'm looking for an algorithm to list all the divisors (not
>necessarily prime) of an arbitrary positive integer. E.g. for 24,
>this algorithm should return
>
> 1 2 3 4 6 8 12 24
>
>I thought this would be easy to find with Google, but to my surprise
>I have not been able to find anything. I suppose that my Googling
>has been exceptionally inept. If anyone can point me in the right
>direction, I'd be most grateful.
>
>kj
>
>P.S. Yes I can code a grossly inefficient monstrosity to generate
>all the divisors, but I'm looking for an algorithm with a clue.
>I imagine there must be a standard for doing this in the general
>case.

First find the prime factorization of the number. Then use the same
prime factorization but allow the exponents to vary (independently)
from 0 to the value of the exponent in the prime factorization.

For example, to find the divisors of 24, first obtain the prime
factorization:

24 = 2^3*3 = 2^3*3^1

Then the positive integer divisors of 24 are precisely the numbers of
the form:

x=2^a*3^b where 0<=a<=3 and 0<=b<=1.

To see this explicitly:

1=2^0*3^0
2=2^1*3^0
3=2^0*3^1
4=2^2*3^0
6=2^1*3^1
8=2^3*3^0
12=2^2*3^1
24=2^2*3^1

So once you have the prime factorization, generating the list of
divisors is easy.

quasi
.

Relevant Pages

  • smallest positive integer that has exactly k divisors
    ... has exactly k divisors. ... number which have 6 divisors.One brute force approach i came across ... is find the prime factorization and calculate the factors until ...
    (comp.programming)
  • smallest positive integer that has exactly k divisors
    ... has exactly k divisors. ... number which have 6 divisors.One brute force approach i came across ... is find the prime factorization and calculate the factors until ...
    (sci.math.research)
  • smallest positive integer that has exactly k divisors
    ... number which have 6 divisors.One brute force approach i came across ... is find the prime factorization and calculate the divisors until ...
    (sci.math)
  • Re: 1, 2, 3, 5, 7... PRIME Numbers
    ... By definition in mathematics, 1 is not a prime number. ... It all gets easier if you say that any positive integer has the ... Categorizing 1 as non-prime isn't the only to think about it. ... integer which has exactly two divisors. ...
    (comp.lang.c)
  • Possible test for divisor of Phi(N)
    ... earlier post "Test for Divisors of Phi" and in particular to Bob ... Pollard Rho factoring algorithm for factoring N = P*Q. ... thousand trial divisors of Phiand assigns a score to each ... residues appearing in that row are less than the maximum P-1 possible. ...
    (sci.crypt)
Loading