Разложение числа на простые делители

Правка ru3, от so_close, 2017-10-07 14:01:39

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

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

Теги теория чисел, математика, конструктив

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский so_close 2017-10-07 14:02:01 18 Tiny change: ' problem: with given N <= 1 00' -> ' problem: for every 1 <= N <= 1 00'
ru3 Русский so_close 2017-10-07 14:01:39 53
en2 Английский so_close 2017-10-07 13:56:03 225
ru2 Русский so_close 2017-10-07 13:53:56 124
en1 Английский so_close 2017-10-07 13:49:49 309 Initial revision for English translation
ru1 Русский so_close 2017-10-07 13:47:16 374 Первая редакция (опубликовано)