how to find prime factorisation of a number?

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
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