Eratosthenes

Prime Numbers

Prime numbers are positive integers that are divisible only by 1 and themselves without a remainder.  Write a program to find the prime numbers between 0 and 1000.

You can use a few tricks to make your program more efficient.  Test all the numbers up to the square root of the number.  If the number has an integer square root, then obviously it has factors other than 1 and itself.

Do you know that mathematicians have never found a formula that can predict with perfect accuracy the spacing of prime numbers?  It seems that there is no regular pattern to their occurrence!

The Sieve of Eratosthenes

One method for finding Prime numbers is:

• Write out the numbers from 1 to 1000.
• Test the first available number on the list for primeness.
• If it is prime, then circle it, and cross off all multiples of that number, making them unavailable.

Repeat this process until you have reached the end of the list, or there are no more uncrossed numbers to process.  The Circled numbers are the primes.

Write a program to find all the primes between 1 and 10 000 using this method.

Credit Blundell@MonktonCoombe

IMAGE CREDIT: https://en.wikipedia.org/wiki/Eratosthenes