Блог пользователя Ehsan_sShuvo

Автор Ehsan_sShuvo, история, 8 лет назад, По-английски

Can anyone please help me to understand the "Segmented Seive"?I have tried myself as i can do enough to get it but unfortunately still now i don't catch it. Thanks in advance!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Let the segment is from left to right.

At first you should generate the set of prime numbers from 1 to sqrt(right).

Now you can get the first number divisible by a prime number p in the segment by this equation St = ((l + p - 1) / p) * p (ceil) Now someone can mark the numbers divisible by p the same way used in normal sieve.