Всем добрый день! Возникла такая задача: для каждого 1 <= N <= 1 000 000, найти все простые делители. Находить степени этих самых простых делителей необязательно. Есть подозрение, что можно использовать решето Эратосфена и какой-то вспомогательный массив, но не могу завершить размышления. Может это и известная задача, не знаю. Кто поможет?

UPD. Следущий алгоритм медленный: делаем решето Эратосфена, потом проходимся по простым числам и проверяем деление. Разложение за O(sqrt(N)) медленное.