Eratosthenes' sieve

One way to find prime numbers up to a given value “x” is to list the positive integers up to and including that number.

Then cross out 1 because 1 is not a prime number

Then take the next integer 2 don’t cross it out but cross out all multiples of it. Repeat this process for all integers up to (and including) the square root of “x”.

(In fact you need only do this for the prime numbers up root “x” but if you are looking for prime numbers you might not know them all and doing all integers is a failsafe method)

As you go further along the list more and more of the numbers will already be crossed out so you will be crossing out fewer and fewer numbers. When you reach root “x” all the numbers you have not yet crossed out are prime.

The question is will there ever reach a point where no matter how big “x” is you won’t have to cross out any more numbers. This would happen is there were a finite number of prime numbers. So are there?

Are there infinite prime numbers?

It is in fact fairly easy to prove that there are infinite prime numbers.

Suppose that there were a finite number of prime numbers.

Then suppose you multiplied them all together.

Then suppose you added one.

The number you would produce is not divisible by any of the other prime numbers because it is one more than multiples of all of them therefore it is either prime or divisible by some other prime number not on the origional list.

You can use this method to generate infinite prime numbers.


2*3*5*7*11*13*17*19*23*29*31*37*41*43*47+1 is not prime but it is a multiple of 127-a prime not on the list.

Thanks to 10998521 for pointing this out