Fastest way to find all the divisors of a large number

Asked Dec 02 '16 at 19:10

Active Dec 02 '16 at 21:11

Viewed 5,743 times

I am facing a problem when I want to get all the divisors of a large number i.e n=10^12. There is a method, which checks all possible numbers less than square root of given number n.

for(int i=1; i<=sqrt(n); ++i){
    if(n%i==0){
        factors.push_back(i);
        if(i!=n/i) factors.push_back(n/i);
    }
}

But when n is very large i.e 10^12 then it needs 10^6 iterations which is very slow.

Is there any faster way when I have all prime divisors of given n such as given number is 48. Then prime factorization of 720 is 2^4 * 3^2 * 5.

All the divisors of 720 are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720.

I have already searched for faster way than O(sqrt(n)). But haven't found.

edited Dec 02 '16 at 21:11

asked Dec 02 '16 at 19:10

Md. Ikramul Murad

Possible duplicate of [Best way to find all factors of a given number in C#](http://stackoverflow.com/questions/239865/best-way-to-find-all-factors-of-a-given-number-in-c-sharp) – Eli Sadoff Dec 02 '16 at 19:12
The non-prime factors are of no interest. You should only be looking. For prime factors. – user207421 Dec 02 '16 at 19:14
nope. I asked for large number. @EliSadoff – Md. Ikramul Murad Dec 02 '16 at 19:14
@Murad the algorithm is the same regardless of the size of the number. – Eli Sadoff Dec 02 '16 at 19:16
@EJP I need all the divisors. – Md. Ikramul Murad Dec 02 '16 at 19:16
@EliSadoff, I haven't seen any solution on that post that works faster than O(sqrt(n)). – Md. Ikramul Murad Dec 02 '16 at 19:18
@Murad The best known right now is O((1/3)exp(64/9)b*log(b)^2)) which is GNFS, where `b` is the number of bits in a number `n`. – Eli Sadoff Dec 02 '16 at 19:21
While it is faster than O(sqrt(n)) the implementation is generally very large to the best of my knowledge. – Eli Sadoff Dec 02 '16 at 19:22
Can you post the pseudo code/c++ code for this approach please? – Md. Ikramul Murad Dec 02 '16 at 19:23

Fastest way to find all the divisors of a large number

0 Answers0

Linked