Finding Primes with Modulo in Python

Question

I have been sweating over this piece of code -- which returns all the primes in a list:

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

print primes

It works... but I don't understand the role "x == i or x % i" plays in the whole thing.

I also don't understand why the second range is only 2 to 7.

I even created a Python implementation of the Sieve of Eratosthenes, hoping that might give me some insight, but it didn't.

When I remove the x % i component, I would expect this code to give me the numbers common to both sets, but it does not:

nums = [2, 20] 
for i in range(2, 8): 
     nums = filter(lambda x: x == i, nums)

print nums

Why is this?

Likewise, when I remove the x == i component, it returns the prime numbers from 11 to 19.

nums = range(2, 20) 

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

print nums

Again, I don't understand why it ignores all primes below 11.

Next, I tried this:

nums = [13] 

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

print nums

Again, this makes no sense to me. The lambda is iterating over x in nums correct? And i is iterating over the range 2 to 7. So, aren't we taking 13 % i... for 2 to 7? How does that result in "13"?

Using the same logic as immediately above, I did the same thing with "13", but using x == i in the lambda.

for i in range(2, 8): 
     nums = filter(lambda x: x == i, nums)

print nums

And as I expected, it returned an empty list -- which makes sense in my mind, because 13 never appears in the range of 2 to 7.

For reference to anyone trying to help, this is the mindset I'm in when I work with filter() and lambdas:

a = range (1, 11)
b = range (9, 20) 

for i in filter(lambda x: x in a, b):
    print i,

This, of course, gives us "9 10". I know the structure of the loop is different, but hopefully it will help you see where my confusion lies.

I have worked with filter() and lambdas somewhat extensively, so I thought I could figure it out, but I'm stumped! I just hope the answer isn't so blindingly obvious that I feel like an idiot...

Answer 1

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]

Answer 2

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: