Prime sieve


As Prime numbers do not have factors, we can rule out any multiple of numbers in our search for Prime numbers.  This is very much a sieve approach where we consider all the numbers and rule out any numbers which are multiples. To start with you may think that we need to consider all numbers, but after further thought we would realise that we need only check numbers which have not appeared before, either as an original number or their multiple. These numbers happen to be Prime numbers and in a way we are searching for Primes using Primes numbers as our base. For this approach to work, we have to assume that all numbers are Prime numbers unless they are shown to be multiples of Primes.  The Sieve of Eratosthenes uses a similar approach by excluding Composite numbers to leave the Prime numbers.
Although it is not explicit, the sieve approach is very much about uncertainty and probability.  The sieve excludes numbers which are not Primes but does not tell you if the numbers left are Primes.  We can only confirm that a number is a Prime by not finding factors and the range that we need to check for each number is from two up to the square root of the number.  If it is a Composite number, we should find a factor within this range and if we don’t we have to assume that it is a Prime.  This is fairly easy for small numbers, but the larger the number the harder it is to confirm that a number is a Prime simply by using the sieve approach.  For example, using the sieve approach and checking multiples of all Prime numbers up to 53 we would exclude most non-primes; but as our range increased we would find that some non-primes were not excluded and we would then not be sure if they were a Prime or Composite number. We would either have to accept an element of uncertainty or need to check more multiples of Primes.
At the top of the sieve, there are a lot of numbers which could be possible Primes, but as we move down, less and less numbers meet the condition and are ruled out, until we find what we believe are the real Primes.  Possible Primes are also called pseudoprimes because they have some properties of Primes, but usually the tests are more rigorous than a simple sieve.

I also post my artwork on my Flickr page



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s