Odd behavior of stacked filter() calls

So I'm getting some interesting behaviour from some filters stacked within a for loop. I'll start with a demonstration:

>>> x = range(100)
>>> x = filter(lambda n: n % 2 == 0, x)
>>> x = filter(lambda n: n % 3 == 0, x)
>>> list(x)
[0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96]

Here we get the expected output. We have a range within a filter within a filter, and the filter conditions are stacking as we want them to. Now here comes my problem.

I have written a function for calculating the relative primes of a number. It looks like this:

def relative_primes(num):
    '''Returns a list of relative primes, relative to the given number.'''
    if num == 1:
        return []
    elif is_prime(num):
        return list(range(1, num))
    result = range(1, num)
    for factor in prime_factors(num):
        # Why aren't these filters stacking properly?                           
        result = filter(lambda n: n % factor != 0, result)
    return list(result)

For whatever reason, the filter is only being applied to the LAST factor in the list acquired from prime_factors(). Example:

>>> prime_factors(30)  
[2, 3, 5]  
>>> relative_primes(30)  
[1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21,开发者_C百科 22, 23, 24, 26, 27, 28, 29]

We can see that no multiples of 2 or 3 were removed from the list. Why is this happening? Why does the above example work, but the filters in the for loop don't?

---

In Python 3.x, filter() returns a generator instead of a list. As such, only the final value of factor gets used since all three filters use the same factor. You will need to modify your lambda slightly in order to make it work.

result = filter(lambda n, factor=factor: n % factor != 0, result)

---

The evaluation of the iterators is lazy. All filters will be evaluated only in the statement

return list(result)

By that time, the value of factor is the last prime factor. The lambda functions only contain a reference to the local name factor and will use whatever value is assigned to that name at the time of execution.

One way to fix this is to convert to a list in every iteration.

As a sidenote, a much easier implementation of this function is

from fractions import gcd
def relative_primes(n):
    return [i for i in range(1, n) if gcd(n, i) == 1]

Edit: If you are after performance instead of simplicity, you can also try this one:

def relative_primes(n):
    sieve = [1] * n
    for i in range(2, n):
        if not sieve[i] or n % i:
            continue
        sieve[::i] = [0] * (n // i)
    return list(itertools.compress(range(n), sieve))

---

If I understood you correctly and Two integers are relatively prime if they share no common positive factors (divisors) except 1. Using the notation to denote the greatest common divisor, two integers a and b are relatively prime if gcd(a,b)==1. then you can use the fractions module in the following way.

from fractions import gcd

num = 30
relative_primes = filter(lambda x: gcd(x,num) == 1, xrange(1,num))