Ehsan_sShuvo's blog

How does Segmented Seive work?
By Ehsan_sShuvo, history, 8 years ago, In English

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!

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply