The Sieve Of Eratosthenes

It is rather easy to determine the prime numbers up to 10, or even 100 given a few minutes. But what if we are interested in determining the number of primes up to 1000, or even 1,000,000? Is there an easy way to do this? Unfortunately not, since primes don't seem to follow any specific pattern. Fortunately we have computers to help us determine extremely large primes. However, there are some techniques that can be applied in order to figuring primes between a certain bound without checking all numbers if they're prime (as that would take much more time).

The Sieve of Eratosthenes

Suppose we want to calculate the number of primes between 1 and 100. We may consider checking each number to see if they're divisible by all positive integers less than it, but clearly, that would take two much time. In actuality, we don't need to check all the primes to determine the answer.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License