Generate a list of primes numbers in Python

This is frequently used as a programming challenge. There are a few ways to do this, but here is one especially interesting way that I've found. For this guide, we'll assume we want a list of all primes under 50.

1

Generating a list of non-primes is much simpler than generating a list of primes. To begin, we need to think about what a prime number is. A prime number is one that is only divisible by 1 and itself. Therefore, if we want to generate a list of non-primes under 50 we can do so by generating multiples.


noprimes = set(j for i in range(2, 8) for j in range(i*2, 50, i))


We are using a set in this case because we only want to include each multiple once. The function range(2, 8) will generate the numbers 2-7. In this example we are using set comprehension to iterate through the numbers 2 through 7. During each iteration we will use the number to iterate through the range 2i through 50 with an interval of i. Hopefully that isn't too complicated! As an example, the first time we iterate through the outer loop, we generate the number 2. Then we iterate through the inner loop using 2 to produce this range: range(4, 50, 2). This produces: 4, 6, 8, 10, etc until we hit 50. Each of these numbers will be added to our noprimes set. The next time through we generate the number 3. Then in our inner loop we will produce range(6, 50, 3) which will add 6, 9, 12, 15, etc to our noprimes set. As you can see, this simply generates multiples. Once we calculate all the multiples through 7 we can be sure that we've generated all of the multiples. Anything 8 or higher will simply duplicate the work we've already done.

2

The second part is easy. Now that we have a list of non-primes, we can use list comprehension to loop through all numbers less than 50. Then we will check to see if each number exists in our noprimes set. If it doesn't exist, we can be sure that it is a prime number.


primes = [x for x in range(2, 50) if x not in noprimes]


This will generate our list of prime numbers less than 50!


[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]