Is there any fast way to find total divisors of a very large number supposedly 10^18. I have tried a method which is of o(n^(1/3)) Forgive me asking direct question without providing any background or something else.
Asked
Active
Viewed 124 times
0
-
Is your number guaranteed to be positive integers? – adnan_e Apr 09 '20 at 07:50
-
Have a look at this: [Fastest way to find all the divisors of a large number](https://stackoverflow.com/questions/40939369/fastest-way-to-find-all-the-divisors-of-a-large-number) – Daemon Painter Apr 09 '20 at 07:50
-
will it be more than 12 items? – Nafiseh Daneshian Apr 09 '20 at 10:14
-
Thanks guys for helping! I was so into my problem I forgot about I have asked question. Finally I have solved my problem. – An0ket_codes Apr 09 '20 at 20:10
1 Answers
0
The fastest algorithm for that would be General number field sieve, probably fits your question.
On this question there is some discussion ongoing about how to efficiently find all divisors. GNFS is used for factorization, so only accounts prime numbers. You'll have to derive all divisors from that, if you need to. How to I find all divisors from prime factorization?
Further reading: A beginner's guide to the Number Field Sieve; Factoring Integers with the Number Field Sieve
Daemon Painter
- 3,208
- 3
- 29
- 44
-
Thanks for helping me out. I solved it using sieve of eratosthenes. – An0ket_codes Apr 09 '20 at 20:14