Geek Answers Handbook

Odd behavior of calls to stacked filter ()

So, I get interesting behavior from some filters laid out in a for loop. I will start with a demo:

>>> 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 result. We have a range inside the filter inside the filter, and the filter conditions add up as we want. Now here is my problem.
I wrote a function to calculate 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 some reason, the filter only applies to the LAST coefficient in the list obtained 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, 22, 23, 24, 26, 27, 28, 29]

We see that multiple 2 or 3 are excluded from the list. Why is this happening? Why does the above example work, but the filters in the for loop do not work?

+5
source share
3

Python 3.x, filter() . , factor, factor. , .

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

.

return list(result)

factor . lambda factor , .

- .

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

. , :

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))
+1

If I understand you correctly and two integers are coprime if they do not have common positive factors (divisors), except 1. Using the notation to denote the greatest common factor, two integers a and b are coprime if gcd (a, b ) == 1. then you can use fractions as follows.

from fractions import gcd

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

More articles:


All Articles