you can use pollard-rho

You can use the SQUFOF algorithm to find a non-trivial factor of $$$n$$$ in $$$O(\sqrt[4]{n})$$$.

First you would want to check if $$$N$$$ is prime by using something like Miller-Rabin primality check which runs in logarithmic time.

If $$$N$$$ is prime then you are done. Otherwise you know that there exists at least one prime integer $$$a$$$ such that $$$a \leq \sqrt{N}$$$ and $$$a \cdot b = N$$$ and $$$a \leq b$$$ for some integer $$$b$$$.

You could iterate through all possible $$$a$$$ and find it but this takes $$$\mathcal{O}(\sqrt{N})$$$ time. However we do not need to iterate that far. It is sufficient to iterate up to the cube root of $$$N$$$, taking $$$\mathcal{O}(\sqrt[3]{N})$$$ time. This would factor all numbers which have at least three prime factors.

If you have not found a prime which divides $$$n$$$ after this iteration, it must be the case that both $$$a$$$ and $$$b$$$ are prime. These numbers are known as semiprimes and Pollard-Rho algorithm can factor these efficiently for you in $$$\mathcal{O}(\sqrt[4]{N})$$$ where $$$p$$$ is a prime which divides $$$n$$$. Therefore the total time complexity would be $$$\mathcal{O(\sqrt[3]{N})}$$$.

You can use Pollard Rho for finding any positive divisor $$$d$$$ of $$$n$$$ in $$$O(n^{1/4})$$$

But it is bad if $$$n$$$ is prime, since $$$d$$$ will be either $$$1$$$ or $$$n$$$ forever

So you need Miller Rabin to check if $$$n$$$ is prime or not, its complexity is $$$O(\log^k n)$$$

In this case, since $$$\max(n) = 10^{18}$$$ is considered large enough, it is better to use Desterministic Miller Rabin which only test for $$$7$$$ integers only

Notice that we can still get rid of another $$$O(\log n)$$$ factors by applying modulo multiplying faster, either by boosting its constant to $$$O\left(\frac{\log n}{w}\right)$$$ (for some $$$w = 2^k$$$) or get rid of it with Fast Mod Mul. Note: Since $$$n \leq 10^{18} \Rightarrow \log n \leq 62$$$, the constant $$$w$$$ can be significant

There are many more trivial optimizations like using constant or constexpr for modulo, using inline functions if needed (tho computer can determine better), and replacing recursive with iterative and cache-friendly.

You can also try to pre-sieve for the first $$$O(n^{1/4})$$$ primes and add some if-conditions for faster factorization special cases

https://en.algorithmica.org/hpc/algorithms/factorization/

You can check out sslotin's blogs for more fast stuff

You can use this algorithm