I was curious about how to go about extracting a list of all prime numbers below a certain number. There was no point to this, just pure curiosity... I found a few solutions on the web, and pieced a few ideas together to form a tidy solution. It's may not be the most efficient, but it works.
I'll put the code below, and then run through the logic line by line:
n = 20 number_range = set(range(n, 1, -1)) primes_list = [] while number_range: prime = number_range.pop() primes_list.append(prime) number_range.difference_update(set(range(prime*2, n+1, prime)))
1. Essentially, what we're wanting to do here is find a list of prime numbers between 1 and n, for the example here let's put n at 20.
n = 20
2. We want to start with the range of numbers between 2 and 20, so we can search through looking for primes (we know 2 is the first, so can set the lowest value in the set to 2). We use a set, as it allows some special functionality later to eliminate non-primes...
number_range = set(range(n, 1, -1))
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
3. We create an empty list, we'll append each prime number as we find them
primes_list = []
4. We want to run through our number range looking for primes, and we want to do this until we've exhausted our number range, so we'll use a while loop
while number_range:
5. We know the first value in our range is a prime, so we can use the in-built Python function 'pop' to extract the first element and remove it from the number_range set. In the first iteration of the loop - this value will be 2
prime = number_range.pop()
6. We append our first prime number to our primes list
primes_list.append(prime)
7. Now, for the prime number we've just removed (in the first iteration this is the number 2, we can remove all multiples of that number in our remaining number_range set and then eliminate these from the set using the 'difference_update' functionality
number_range.difference_update(set(range(prime*2, n+1, prime)))
What this 'difference_update' functionality means, is that:
Our number set: {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} (remember we 'popped' 2 out of the set, so it now starts at 3)...
Becomes: {3, 5, 7, 9, 11, 13, 15, 17, 19}
Because all multiples of 2 {4, 6, 8, 10, 12, 14, 16, 18, 20} are removed.
8. The while loop now runs again, and what do you know...the first number in the list is the next prime number, so gets added to our Primes list
So if we were to run all our code - we get our list of primes!
n = 20 number_range = set(range(n, 1, -1)) primes_list = [] while number_range: prime = number_range.pop() primes_list.append(prime) number_range.difference_update(set(range(prime*2, n+1, prime)))
print(primes_list) [2, 3, 5, 7, 11, 13, 17, 19]
Let's turn this into a function, and see how long it takes to run for some larger number ranges.
import time def prime_finder(n): number_range = set(range(n, 1, -1)) primes_list = [] while number_range: prime = number_range.pop() primes_list.append(prime) number_range.difference_update(set(range(prime*2, n+1, prime))) return primes_list
t0 = time.time() primes_list = prime_finder(1000) time.time() - t0
Primes to 1,000 took 0.001 seconds. Primes to 1,000,000 took 0.31 seconds. Primes to 10,000,000 took 3.33 seconds Primes to 100,000,000 took 40 seconds Primes to 1,000,000,000 ran out of memory...I guess we are creating a pretty large set of numbers in the first instance!
For interests sake, we can also look at how many primes were found, and also what the largest one was:
print(len(primes_list)) print(primes_list[-1])
In our range up to 100 million, we found 5,761,617 prime numbers, with the largest being 95,462,681