Algorithm to find all the divisors of any number

general
, ,
1

how we can find divisors of any number

1 Like
2

use sieve of erathos

3

Hi,

Looping from 1 to N-1 would yield a O(N) algorithm and when N can go as high as 10^12 you will get in trouble. For that, you can use an algorithm which takes advantage of the fact that sqrt(N^2) = N.

This means that if you loop from i = 1 to int(sqrt(N)) you can find all the divisors like this:

If i divides N, then it’s a divisor. Then, you can also add to the list the value N/i, which will also be a divisor.

This yields an O(sqrt(N)) algorithm.

Best,

Bruno

3 Likes
4

Brother, you’ll get all your answers here:-


To learn Number Theory interactive way : http://www.math.mtu.edu/mathlab/COURSES/holt/dnt

1 Like