God may not play dice with the universe, but something strange is going on with the prime numbers.
Paul Erdos
A prime number is a positive number greater than 1, which has no positive integer divisors except 1 and itself. Therefore, numbers like 2, 3, 5, 7, 11 are all prime numbers.
As a result of the definition of a prime number, one might probably decide to check if a given number, x, is prime by trying to divide it by all the integers starting from 2 and smaller than x. If no such number divides x evenly, then it can be concluded that x is a prime number. Although such a method can be used for very small numbers, but it will be very time consuming and also subject to errors for large numbers. For instance, if x=100,000,000, then the program must check each and every number between 2 and 99,999,999 to see if it divides x evenly or not.
Better methods can nevertheless be used to calculate prime numbers. One of the most efficient algorithms for calculating prime numbers is called Sieve of Eratosthenes. Put simply, this algorithm starts from the very first prime number, 2, and marks every multiple of it smaller than x as composite. Then the algorithm continues with the next prime number. The remaining numbers will be primes. The following animation, adapted from Wikipedia, clearly illustrates this algorithm.
Let’s have a quick look at the code which does this for us:
[pastacode lang=”python” manual=”%0A%0A%0A%22%22%22Econowmics.com%22%22%22%0A%0Adef%20Sieve(n)%3A%0A%20%20%20%20%22%22%22This%20function%20calculates%20all%20prime%20numbers%20up%20to%20a%20given%20limit(n)%22%22%22%0A%20%20%20%0A%20%20%20%20%23Defining%20the%20inintial%20list%2C%20all%20equal%20to%20True%0A%20%20%20%20primes%20%3D%20%5BTrue%20for%20i%20in%20range(n%2B1)%5D%0A%20%20%20%20primes%20%5B0%5D%20%3D%20primes%20%5B1%5D%20%3D%20False%0A%0A%20%20%20%20%23The%20starting%20number%0A%20%20%20%20p%20%3D%202%0A%0A%20%20%20%20%23Running%20a%20loop%20to%20check%20all%20numbers%20below%20the%20square%20root%20of%20the%20given%20number%0A%20%20%20%20while%20p%20**%202%20%3C%20n%3A%0A%20%20%20%20%20%20%20%20%23Check%20to%20see%20if%20it%20is%20equal%20to%20True%20(if%20the%20number%20is%20prime%20or%20not)%0A%20%20%20%20%20%20%20%20if%20primes%5Bp%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23If%20it%20was%20a%20prime%20number%2C%20kill%20every%20other%20multiple%20of%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20number%20in%20range(p*2%2C%20n%2B1%2C%20p)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20primes%5Bnumber%5D%20%3D%20False%0A%0A%20%20%20%20%20%20%20%20%23Increment%20the%20starting%20number%20by%20one%20to%20keep%20the%20loop%20working%0A%20%20%20%20%20%20%20%20p%20%2B%3D%201%20%0A%0A%20%20%20%20prime_numbers%20%3D%20%5Bi%20for%20i%20in%20range%20(n%2B1)%20if%20primes%5Bi%5D%3D%3DTrue%5D%0A%20%20%20%20%23If%20you%20want%20to%20see%20the%20list%20of%20prime%20numbers%20in%20the%20output%0A%20%20%20%20%23return%20prime_numbers%0A%0A%20%20%20%20%23If%20you%20want%20to%20see%20how%20many%20prime%20numbers%20are%20there%20in%20a%20given%20range%0A%20%20%20%20return%20len(prime_numbers)” message=”” highlight=”” provider=”manual”/]
First, we define a list equal to the size of n, with all elements equal to True. As the algorithm runs, those indexes of this list that are marked as composite will be changed to False. Before the loop, we set the first two instances, namely 0 and 1, which are not primes, into False.
Then, we define the starting number, p=2.
In the next step, we start a loop to check all the numbers below the square root of the number we are looking for. The reason why we only check the numbers below the square root can be seen from this photo:
After the square root, the numbers just repeat themselves and it would be of no use to check the other numbers.
Now, if the number in the index that we are checking is actually a prime, we set all of its multiples as composite, i.e. set them to False (not primes).
Then we increment p by 1 to check the next number. This goes on until the condition of the while-loop turns False.
In the last step, we can return the result that we want. For example, here two options are given. Depending on each one suits you best, you have to uncomment it. Here, we check for the total amount of primes less than a given number.
Let’s test the function:
[pastacode lang=”python” manual=”import%20time%0A%0A%23marking%20the%20starting%20time%0Astart%20%3D%20time.time()%0A%0A%23For-loop%20to%20evaluate%20the%20function%0Afor%20i%20in%20%5B10%2C100%2C1000%2C10000%2C100000%2C1000000%2C10000000%2C100000000%5D%3A%0A%20%20%20%20print%20(%22There%20are%20%22%20%2B%20str(Sieve(i))%20%2B%20%22%20prime%20numbers%20below%20%22%20%2B%20str(i)%20%2B%20%22.%22)%0A%0A%23marking%20the%20end%20of%20time%20and%20calculating%20the%20total%20duration%20%20%0Aend%20%3D%20time.time()%0Aduration%20%3D%20end%20-%20start%0Aprint%20(duration)” message=”” highlight=”” provider=”manual”/]
Which results in:
Also watch
Further reading on prime numbers
The Largest Known prime by Year: A Brief History
Prime Numbers–Why are They So Exciting?
Why Prime Numbers Still Surprise and Mystify Mathematicians
unusual and physical methods for finding prime numbers