Prime numbers have been understood at least since the Ancient Greeks, and possibly since the Ancient Egyptians. In modern times their study has intensified greatly due to their usefulness, notably in encryption, and because computers enable them to be calculated to a massively higher level than could be done by hand.
The best know (and according to Wikipedia still the most widely used) method for identifying them is the Sieve of Eratosthenes, which I will implement here in Python.
The Sieve of Eratosthenes
The algorithm is described in full on Wikipedia, and you might like to take a look at the article.
To summarize the process:
- Create a list of integers from 2 to the highest number you want to check, marking them all as prime
- Initialize a variable p to 2 (the lowest prime)
- Mark all multiples of p as composite (ie. non-prime)
- Set p to the next number marked as prime
- Repeat 3 and 4 until no subsequent primes are found.
The algorithm as it stands has some glaring inefficiencies and the Wikipedia article cited above does include some refinements and alternatives. Nevertheless, let's get stuck into a simple and straightforward implementation in Python.
Writing the Code
Create a folder and within it create an empty file called sieveoferatosthenes.py. You can download the source code as a zip or clone/download the Github repository if you prefer.
Source Code Links
ZIP FileGitHub
This is the entire source code listing.
sieveoferatosthenes.py
PRIME_COL="\x1B[32m"COMPOSITE_COL="\x1B[31m"RESET_COL="\x1B[0m"defmain():"""Themainfunctioncreatesandrunsthesieve,usingthevariousotherfunctionsbelow."""print("-------------------------")print("| codedrome.com |")print("| Sieve of Eratosthenes |")print("-------------------------\n")#Createalistofspecifiedsize,initiallyallsettoTruemax=200sieve=[True]*(max+1)p=2print("Initialstate:allmarkedasprime")print_sieve(sieve,10)print("RunningSieveofEratosthenes...")while(p!=-1):mark_multiples(sieve,max,p)p=find_next_prime(sieve,max,p)print("Compositenumbersnowidentified")print(PRIME_COL+"Primenumbers"+RESET_COL)print(COMPOSITE_COL+"Compositenumbers"+RESET_COL)print_sieve(sieve,10)defprint_sieve(sieve,columncount):"""Printsthesieveincolumnsofspecifiedsize.Primesandcompositesareprintedinthecoloursspecifiedatthetopofthefile,usingANSIterminalcodes."""foriinrange(1,len(sieve)):ifsieve[i]==True:print(PRIME_COL+"%4d"%i+RESET_COL,end="")else:print(COMPOSITE_COL+"%4d"%i+RESET_COL,end="")ifi%10==0:print("")defmark_multiples(sieve,max,p):"""Givenaprime,markallitsmultiplesasFalse(ienon-primeorcomposite)uptothegivenmaximum."""multiplier=2i=p*multiplierifi<=max:while(i<=max):sieve[i]=Falsemultiplier+=1i=p*multiplierdeffind_next_prime(sieve,max,current):"""Iteratesremainingpartofsievetofindnextprime.Returnsitiffound,or-1ifitgetstotheendwithoutfindinganymoreprimes."""foriinrange(current+1,max+1):ifsieve[i]==True:returnireturn-1;#-----------------------------------------------------main()
Firstly we have some strange looking variable initialisations (with uppercase names to signify that they should be regarded as constants) which are used to output composite and prime numbers in red and green respectively, using ANSI codes.
In main we create a max variable to specify how far we want to go in our prime hunt, and then create a list of Booleans of that size, all set to True for the time being. As you may have realised, although the Sieve of Eratosthenes is usually described as an algorithm for identifying prime numbers it is actually the opposite. It starts off with the assumption that all numbers are prime, and then identifies the ones that are not. This initial state is printed to emphasise the process.
We then enter a while loop, calling functions to flag multiples of p as composite and then getting the next prime in the list. The latter function returns -1 if there are none left, so that value is used as the exit condition of the while loop.
The process is now complete so we just call print_sieve again to show which numbers are prime and which are composite.
Now we just need to implement the three functions called in main, starting with print_sieve. This iterates the data, outputting the values in red or green to indicate their status as composite or prime - note we start off with a key to the colour coding.
The function takes a columncount argument so if we have run out of columns we print a new line to go back to the first column. This is calculated using the modulus (remainder) operator %, for example if we asked for 10 columns and have just printed value 30, 30 % 10 = 0 so we call print("") with an empty string so it will just print a new line. For any value of i which is not a multiple of 10 the modulus will be non-zero so print("") is not called.
Now let's move on to the core function of this entire project: mark_multiples.
Firstly we create a couple of variables, one for the multiplier set to 2 and another called i which is set to p * multiplier to give us the first value to flag as non-prime. After checking that i hasn't blown through the end of the data we enter a while loop, setting the flag to false, incrementing the multiplier, and then calculating the next value of i or in other words the next value to be flagged as non-prime. The loop continues until we run past max.
Basically what we are doing here is multiplying the current prime by 2, 3, 4 etc. and marking the result as non-prime until we get past max. Note this is one of the inefficiencies in the basic algorithm - we may be marking numbers as non-prime which have already been flagged as multiples of lower primes. For example, 6 would be marked as non-prime because it is a multiple of 2, but would be marked non-prime again as a multiple of 3.
Finally we will implement find_next_prime. This function searches through the flags for the next prime, starting at the one after the current. If one is found it is returned; if the loop completes without a prime being found the function returns -1. (Remember that in main we use -1 as the terminating condition for the while loop.)
Now we can run the program - enter this in terminal:
Running the program
python3.7 sieveoferatosthenes.py
The program output looks like this for max = 100. First we see all the numbers in green as they are initially marked as prime, then the numbers again with the composites in red. You could call print_sieve within the loop in main if you want to see the progress of each iteration, although it might be rather tedious for this many numbers.
Program Output
-------------------------|codedrome.com||SieveofEratosthenes|-------------------------Initialstate:allmarkedasprime123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200Running Sieve of Eratosthenes...Composite numbers now identifiedPrime numbersComposite numbers123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
Please follow CodeDrome on Twitter to keep up to date with new posts.
