* Disclaimer: I have tested none of this code yet. Please do share if you find a syntactic error here. 🙂 I’m trying to practice my ability to write code without an editor and without testing every little step as I build it.
This question came up about a week and a half ago and it wasn’t directly asked of me, but I was intrigued enough to finally dig into it. This is something that’s come up in various projects for school and once in a hackerrank challenge for me. My brain likes to scream “There has to be a better way!” at me as I hack my way on through to get things done because I just don’t have the time to dig into it.
Speaking of hacking on through, always start with brute force. 🙂 Why? The first step in any problem is to prove there’s a viable solution. Only then should we start to work on optimization. Even in my world of databases I’ve made the mistake of trying to optimize first and worked myself into a corner. So, how do we know if something is prime? Test if it’s divisible by any number other than 1 and itself. As far as the algorithm goes, this would be a simple loop.
Given n is the number you’re testing, it would look something like this:
def isPrime(n):
# test shouldn't include 1 or the number
for num in range(2, n):
if n % num == 0:
return False
return True
For one number, this is fine. What happens if you start looking at multiple numbers though? You end up recalculating the same number several times. Another way to look at it is if you were to save the prime numbers you’ve found so far and use those up until the max number.
The following code is similar to the first in that it only does the calculation for one number, but the saved primes require less divisibility tests to occur. There are much nicer ways of handling the prime list but I’m going to keep it simple here.
# starting off with just the first two
# for demonstration purposes :)
primes = [1, 2]
def isPrime(n, primes):
# test division by found primes
for num in primes:
if n % num == 0:
return False
maxPrime = primes[-1]
for i in range(maxPrime+1, n):
if n % i == 0:
return False
return True
In the last code section, I didn’t have it store the prime number. That was intentional. The idea there was to have the primes be sequential and there’s nothing in that function enforcing that n is sequenced. So really what we need is a function to calculate primes sequentially that we can store – and we could use this existing function if desired! I will, because it’s easier for me. 🙂 The basic psuedocode I figured out for myself was this: for each number i where maxPrime < i <= n, if the number is prime, add it to the list.
primes = [1, 2]
# primes through n using memoized list
def calcPrimes(n, primes):
# for each number maxPrime through n (maxPrime, n]
maxPrime = primes[-1]
for i in range(maxPrime+1, n+1):
# if number is prime - add to list
if isPrime(i, primes):
primes.append(i)
Realistically, the best way to do it for most cases would be with one of my favorite things from my undergrad. I had completely forgotten about it but when I started looking up efficient ways to calculate primes it jumped out at me as an old friend. I didn’t remember the details, but I certainly remembered the joy associated with learning the Sieve of Eratosthenes 10 years ago. Rather than using an additive approach to build a list of primes, it uses elimination of all multiples in the range. So for example, if we were calculating all primes up to 50, it would first eliminate all multiples of 2 in the range, then 3, then 5 – because 4 was already eliminated as a multiple of 2 – and so on. The one major pitfall with this is the space required to store the full list of numbers.
For the sake of time and accuracy, I’ve borrowed an implementation from Geeks for Geeks. 🙂 This is really the important part of this exercise – the efficient implementation we’ve been driving toward!
# Python program to print all primes smaller than or
# equal to n using Sieve of Eratosthenes
def SieveOfEratosthenes(n):
# Create a boolean array prime[0..n] and initialize
# all entries it as true. A value in prime[i] will
# finally be false if i is Not a prime, else true.
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
# If prime[p] is not changed, then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p * 2, n+1, p):
prime[i] = False
p += 1
# Print all prime numbers
for p in range(2, n):
if prime[p]:
print p,
# driver program
if __name__=='__main__':
n = 30
print "Following are the prime numbers smaller",
print "than or equal to", n
SieveOfEratosthenes(n)
If you wanted to build a list of primes from this, you could create a list and append them instead of printing, like this:
# aggregate all prime numbers
primes = []
for p in range(2, n):
if prime[p]:
primes.append(p)
print primes
# allow use outside the function
return primes
As a fun challenge, figure out if you could make the primes list using list aggregation instead. It’s a one-liner instead of three and one of my favorite features of Python. I can’t just give you everything. 😉