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...
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 --
x == 1x % 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]