Hello everybody! Got next problem: for every 1 <= 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
Sieve of Erathostenes. Whenever you find a prime p, mark all numbers kp as divisible by it. You can't do any better, since this runs in O(size of your output).
Are you required to explicitely factor all of numbers in 1..N?
The most suitable solution seems to be here.
For those who don't speak Russian:
lpis lowest prime factor andpris with the prime numbers, everything else should be clear from the code.