so_close's blog

By so_close, history, 7 years ago, translation, In English

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

  • Vote: I like it
  • -10
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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).

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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: lp is lowest prime factor and pr is with the prime numbers, everything else should be clear from the code.