DIVISORS OF A NUMBER

general
1

HOW TO CALCULATE ALL DIVISORS OF A VERY LARGE NUMBER??

2

can u give the problem link?

3

Please see this link to editorial for the problem Product of divisors from easy section. Also you might find this helpful

1 Like
4

Hello @monel1994,

If I understood your question correctly and if you want to list all divisors of a large number that is representable with built-in data types (like say, all divisors of 1015 or 1018), there is a way to list all of them relatively fast, with an algorithm that runs in O(sqrt(N)) time.

The above complexity can be achieved by realizing that if a number can be written as the product of two numbers, then that means that those two numbers evenly divide that number, so say, if we have:

12 = 3*4,

if we search up to 3, and divide it by 12, we obtain 4, by searching only up to 3.

This can be generalized to obtain the upper search limit as the sqrt(N) by realizing that x = sqrt(x) sqrt(x).

So, to “make up” for the missing factors, we simply search until the sqrt(N) and divide it by N to obtain the remaining ones.

In a functional-style Python this can be written as:

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

Best regards,

Bruno

1 Like