How can I find the prime factorisation of a large number in linear time?
large number implies that n>=10^9 and n<=10^18
and
Is there any method to find the prime factorisation in constant time?
Can anyone help me…?
If you are interested in number of divisors you can do that in O(n^(1/3)) which is approx 1e6 for n=1e18.
But finding prime factorization at best takes somewhat around sqrt(n) which is feasible for 1e9 but not 1e18.
1 Like