Tutorial for Number Theory Sieve |
The Sieve technique is used for finding prime numbers
Start with all integers in the range 1 to N.
Remove all multiples of 2.
Then remove all multiples of 3.
Then remove all multiples of 4.
Carry on, till the point that the sieve does not change any more.
This is the well know Prime Number Sieve technique.
A C Program for the Sieve of Eratosthenes is available here. The gaps between successive prime numbers increase in a non-linear fashion, if one were to take the moving average. The 34th prime number is 139, 35th prime number is 149,39th prime number is 151 and 40th prime number is 171.