I pass this problem with Sieve of Eratosthenes, but i think solution with Pollard's rho algorithm is funnier, and wrote it too.

If you cant pass it with this algo just use all prime modules from 1'000'000'007 to 1'000'001'393.

Did you check small dividers? ro pollard works very poorly with them

If TL let me check all with O(sqrt(n)), I do it. I invoke rho pollard only if can not pass test with O(sqrt(n))