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
This is the entire source code listing.
sieveoferatosthenes.py
PRIME_COL = "\x1B[32m" COMPOSITE_COL = "\x1B[31m" RESET_COL = "\x1B[0m" def main(): """ The main function creates and runs the sieve, using the various other functions below. """ print("-------------------------") print("| codedrome.com |") print("| Sieve of Eratosthenes |") print("-------------------------\n") # Create a list of specified size, initially all set to True max = 200 sieve = [True] * (max + 1) p = 2 print("Initial state: all marked as prime") print_sieve(sieve, 10) print("Running Sieve of Eratosthenes...") while(p != -1): mark_multiples(sieve, max, p) p = find_next_prime(sieve, max, p) print("Composite numbers now identified") print(PRIME_COL + "Prime numbers" + RESET_COL) print(COMPOSITE_COL + "Composite numbers" + RESET_COL) print_sieve(sieve, 10) def print_sieve(sieve, columncount): """ Prints the sieve in columns of specified size. Primes and composites are printed in the colours specified at the top of the file, using ANSI terminal codes. """ for i in range(1, len(sieve)): if sieve[i] == True: print(PRIME_COL + "%4d" % i + RESET_COL, end="") else: print(COMPOSITE_COL + "%4d" % i + RESET_COL, end="") if i % 10 == 0: print("") def mark_multiples(sieve, max, p): """ Given a prime, mark all its multiples as False (ie non-prime or composite) up to the given maximum. """ multiplier = 2 i = p * multiplier if i <= max: while(i <= max): sieve[i] = False multiplier+=1 i = p * multiplier def find_next_prime(sieve, max, current): """ Iterates remaining part of sieve to find next prime. Returns it if found, or -1 if it gets to the end without finding any more primes. """ for i in range(current + 1, max + 1): if sieve[i] == True: return i return -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 | | Sieve of Eratosthenes | ------------------------- Initial state: all marked as prime 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 Running Sieve of Eratosthenes... Composite numbers now identified Prime numbers Composite numbers 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
Please follow CodeDrome on Twitter to keep up to date with new posts.