Нахождение простых чисел с модулем в Python

Я потел над этим фрагментом кода, который возвращает все простые числа в списке: 

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

print primes

Это работает... но я не понимаю, какую роль "x == i or x % i" играет во всем этом.

Я также не понимаю, почему второй диапазон составляет только от 2 до 7. Я даже создал Python-реализацию сита Эратосфена, надеясь, что это даст мне некоторое представление, но этого не произошло.

Когда я удаляю компонент x % i, я ожидаю, что этот код даст мне числа, общие для обоих множеств, но это не так: 

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

print nums

Почему это?

Аналогичным образом, когда я удаляю компонент x == i, он возвращает простые числа от 11 до 19. 
nums = range(2, 20) 

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

print nums
Опять же, я не понимаю, почему он игнорирует все простые числа ниже 11.

Затем я попробовал это: 

nums = [13] 

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

print nums
Опять же, это не имеет для меня никакого смысла. Лямбда повторяется над x в nums правильно? И i повторяется в диапазоне от 2 до 7. Итак, разве мы не берем 13 % i... от 2 до 7? Как получается ли это "13"? Используя ту же логику, что и непосредственно выше, я сделал то же самое с "13", но используя x == i в лямбде. 
for i in range(2, 8): 
     nums = filter(lambda x: x == i, nums)

print nums
И, как я и ожидал, он вернул пустой список - что имеет смысл в моем уме, потому что 13 никогда не появляется в диапазоне от 2 до 7.

Для справки о тех, кто пытается помочь, это образ мышления, в котором я нахожусь, когда работаю с filter() и лямбдами: 

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

for i in filter(lambda x: x in a, b):
    print i,
Это, конечно, дает нам "9 10". Я знаю структуру петли это другое, но, надеюсь, это поможет вам увидеть, где лежит моя путаница.

Я работал с filter() и лямбдами довольно широко, поэтому я думал, что смогу понять это, но я в тупике! Я просто надеюсь, что ответ не настолько очевиден, чтобы я чувствовал себя идиотом...

4 5
python lambda primes modulus

4 ответа:

Это выглядит как компактная (но несколько неясная) реализация сита Эратосфена [EDIT: как указано в комментариях, это на самом деле" неверное сито", поскольку пробное разделение вызывает худшую временную сложность, чем фактическое сито Эратосфена].

Первая строка-это просто произвольный диапазон поиска последовательных целых чисел для фильтрации простых чисел: 
primes = range(2, 20)

Далее, следуя алгоритму сита , мы повторяем с целым числом i в диапазоне (2, n) где n-наивно самое большое число в диапазоне поиска (хотя в этом случае 7-выбранная верхняя граница-подробнее об этом ниже).

for i in range(2, 8): 
    primes = filter(lambda x: x == i or x % i, primes)
Алгоритм утверждает, что мы включаем i и исключаем кратные i. Вот для чего нужен фильтр лямбда-предикатов --
  • включить i: x == 1
  • исключите кратные i: x % i - это короткая рука для x % i != 0. Другими словами, x не делится на i, или, наоборот, x не кратно i.
Верхняя граница 8 кажется несколько произвольной - как минимум, нам нужно искать только до sqrt(n), так как sqrt(n) * sqrt(n) = n означает, что sqrt(n) является верхней границей пространства поиска. Квадратный корень из 19 равен приблизительно 4,4, и в этом примере вы видите, что список простых чисел не изменяется после 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]
3

Первый блок кода, который вы опубликовали, является самым простым примером для меня, чтобы объяснить это: 

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

При использовании метода сита Эратосфена важно отметить, что вам нужно только удалить числа, которые являются произведениями чисел до квадратного корня из max. Использование range(2,8) выше реализует это (оно идет от 2 до 7, что дальше, чем необходимо). Квадратный корень из 19 (наибольшее число во внешнем диапазоне, которое проверяется) находится между 4 и 5. Таким образом, наибольшее число, которое должно быть проверено в диапазоне, равно 4 (нам нужно только проверить целые числа).

Используя эти знания, вы можете улучшить код следующим образом (это находит простые числа 

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
Обратите внимание, что вместо использования floor и последующего добавления одного, поскольку range является исключительным, я использую ceil.

Запустите его здесь: http://repl.it/8N8

Edit: я также понял, что это (и код, приведенный в вопросе) не является полной реализацией метода sieve, поскольку в соответствии с алгоритмом мы должны только помечать кратные простые числа , это означает, что внутреннее использование range не так эффективно, как должно быть.

Увидеть графическое изображение алгоритма в прогресс:

решето Эратосфена

2

Я написал простой список понимания для генерации простых чисел. Конечно, основная идея была скопирована в переполнении стека. Честно говоря, мне потребовалось время, чтобы понять это, поскольку я был новичком в python. Я использовал этот список понимание путем вызов лямбда-функции отдельно. Поэтому сначала я рассмотрю лямбда-функцию.

лямбда-функция: is_prime = lambda x: all(x % y != 0 для y в диапазоне (2, int (math.sqrt (x)) + 1))

Теперь понимание списка с помощью выше лямбды.

Простые числа = [x для x в диапазоне (30), если is_prime (x) = = True]

1

Я думаю, что ответ довольно прост. Увеличьте набор простых чисел с диапазона (2,20) до диапазона(2,30) и повторите мысленный эксперимент. Это будет мне гораздо более очевидно.

Функция фильтра будет возвращать значения для диапазона диапазона (2,20), что 

filter(lambda x: x == i or x % i, primes)

Возвращает true.

В дополнение к увеличению простых чисел от диапазона (2,20) до диапазона (2,30), поиграйте с вашими внутренними критериями фильтра, и вы начнете видеть различия, которые вы ищете для.

#!/usr/bin/python

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

print primes

В результате чего: 

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]

И 

#!/usr/bin/python

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

print primes

Приводит к 

[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29]
-1