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

Revision en2, by so_close, 2017-10-07 13:56:03

Hello everybody! Got next problem: with given N <= 1 000 000 we need to found all prime divisors of N. Moreover, we aren't required to know their powers — only primes themselves. I guess we can use Eratostenes algorithm, but I can't finish my solution. Who can help?

UPD. Solutions like trivial O(sqrt(N)) and similar, as well as doing Eratostenes and then, for example, got an array prime[] with primes, iterating that array and checking them are too slow. We need something faster

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English 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 Russian so_close 2017-10-07 14:01:39 53
en2 English so_close 2017-10-07 13:56:03 225
ru2 Russian so_close 2017-10-07 13:53:56 124
en1 English so_close 2017-10-07 13:49:49 309 Initial revision for English translation
ru1 Russian so_close 2017-10-07 13:47:16 374 Первая редакция (опубликовано)