Finding Primes with Modulo in Python

The first code block you posted is the easiest example for me to explain this:

primes = range(2, 20) 
for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes)
print primes

When using the Sieve of Eratosthenes method, the important thing to note is that you only have to remove numbers that are products of numbers up to the square root of the max. The use of range(2,8) above implements this (it goes from 2 to 7, which is further than necessary). The square root of 19 (the highest number in the outer range that is checked) is between 4 and 5. So the highest number that should be checked in the range is 4 (we only need to check integers).

Using this knowledge, you could improve the code to be as follows (this finds primes <= 19):

import math
max = 19    #Set it here
max += 1
primes = range(2, max) 
for i in range(2, int( math.ceil(math.sqrt(max)) )): 
    primes = filter(lambda x: x == i or x % i, primes)
print primes

Note that instead of using floor and then adding one because range is exclusive, I use ceil.

Run it here: http://repl.it/8N8

Edit: I also realized this (and the code provided in the question) isn't a complete implementation of the sieve method, since according to the algorithm, we should only flag multiples of primes, meaning that the inner use of range is not as efficient as it should be.

See a graphical illustration of the algorithm in progress:

It looks like a compact (but somewhat obscure) implementation of the Sieve of Eratosthenes [EDIT: as pointed out in the comments, this is in fact an "unfaithful sieve" as the trial division causes worse time complexity than the actual Sieve of Eratosthenes].

The first line is just an arbitrary search range of consecutive integers to filter for primes:

primes = range(2, 20)

Next, following the sieve algorithm, we iterate with integer i in range (2, n) where n is naively the largest number in the search range (though in this case, 7 is the chosen upper bound -- more on this below).

for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes)

The algorithm states that we include i and exclude multiples of i. That's what the lambda predicates filter for --

• include i: x == 1
• exclude multiples of i: x % i -- this is short hand for x % i != 0. In other words, x is not divisible by i, or alternatively, x is not a multiple of i.

The upper bound of 8 seems somewhat arbitrary -- minimally, we only need to search up to sqrt(n), since sqrt(n) * sqrt(n) = n means that sqrt(n) is an upper bound on the search space.

The square root of 19 is approximately 4.4, and in this example you see that the list of primes does not change after i = 3.

In [18]: primes = range(2, 20)

In [19]: for i in range(2, 8):
   ....:     primes = filter(lambda x: x == i or x % i, primes)
   ....:     print i, primes
   ....:
2 [2, 3, 5, 7, 9, 11, 13, 15, 17, 19]
3 [2, 3, 5, 7, 11, 13, 17, 19]
4 [2, 3, 5, 7, 11, 13, 17, 19]
5 [2, 3, 5, 7, 11, 13, 17, 19]
6 [2, 3, 5, 7, 11, 13, 17, 19]
7 [2, 3, 5, 7, 11, 13, 17, 19]