Факторизация числа за N<sup>1/4</sup>. Умножение по модулю с double-ами. Решето Эратосфена за O(N).
Подробнее: plan & code