Список понимания без фильтра

Question

Недавно наткнулся на этот кусок кода онлайн:

nonprime = [j for i in range(2, 8) for j in range(i*2, 50, i)]

Код выше, кажется, вычисляет все простые числа ниже 50, но я не понимаю логику. Я изучил списки в Python и заметил, что он использует фильтр для фильтрации по условиям, но все, что я не могу понять, как два цикла for вычисляют эти не простые числа.

Answer 1

В основном он рассчитывает все кратные значения из диапазона (2, 8) ниже 50. Он будет содержать дублированных значений.

# iterates over values in this range [2, 7]
for i in range(2, 8)

# iterates over multiples of i lower than 50
for j in range(i*2, 50, i)

Результат будет выглядеть следующим образом:

[ 4, 6, 8, ... # multiples of 2 lower than 50
 6, 9, 12, ... # multiples of 3 lower than 50
(...)
14, 21, 28, ... # multiples of 7 lower than 50
]

Answer 2

Вот версия этого кода, не связанная со списком:

nonprime = []
for i in range(2, 8):
    for j in range(i*2, 50, i):
        nonprime.append(j)

Шаг за шагом:

for i in range(2, 8):

Пока все довольно просто. Это вернет числа от 2 до 7, останавливаясь, когда оно достигает 8. В первой итерации этого цикла, i = 2.

    for j in range(i*2, 50, i):

Теперь мы создаем внутренний цикл. Давайте заменим i на 2, чтобы мы могли видеть, что он делает на первой итерации external loop.

    for j in range(2*2, 50, 2):

или

    for j in range(4, 50, 2)

Возвращает список чисел, начинающихся с 4 и увеличивая каждый раз 2 (6, 8, 10), и останавливается, когда он достигает 50. Если вы посмотрите на результаты в nonprime, вы увидите эти числа .

Следующая итерация внешнего цикла, i = 3. Итак:

    for j in range(i*2, 50, i):

становится:

    for j in range(3*2, 50, 3):

Или:

    for j in range(6, 50, 3):

Начиная с 6, мы продолжаем добавлять 3 и останавливаемся, когда получаем 50. Вы увидите, что эта последовательность появится следующей в списке значений в nonprime

Вот и все, что делает весь этот код. Как заметил @Bakuriu, это в основном Сито Эратостенов в обратном порядке, но это уже другая тема.

Answer 3

Это понимание списка делает то же самое, что эти два вложенных цикла for:

nonprime=[]
for i in range(2,8):
    for j in range(i*2, 50,i):
        nonprime.append(j)

Итак, во внешнем цикле i просто увеличивается на единицу в каждой итерации и принимает значения i =2,3,4,5,6,7.Внутренний цикл for j зависит от внешнего цикла.Он начинается в 2*i, а j увеличивается на i в каждой итерации.

Таким образом, для ì=2 внутренний цикл начинается в j=4, а j принимает значения j=4,6,8,...,48.Затем ì увеличивается до 3 во внешнем цикле, а j принимает значения 6,9,12,...48

Обратите внимание, что список nonprime не создает уникальных элементов, так как, например, 6 выглядит болееодин раз.

Как справедливо отмечает Бакуриу, этот метод использует Сито Эратосфена

Answer 4

Ключ к этому ответу лежит в математике:

Если число n> 1 не простое, то оно имеет простой множитель <= sqr (n) </a>

Теперь нам осталось объяснить логику. Обратите внимание, что sqrt(50) < 8, что является пределом первого range.

Мы можем переписать понимание вложенного списка как обычный цикл. Мы можем использовать set вместо списка, который будет содержать ненужные повторяющиеся элементы:

res = set()

for i in range(2, 8):
    for j in range(i*2, 50, i):
        res.add(j)

Внешний цикл повторяет все i < sqrt(50).

Внутренний цикл повторяет, для каждого i, все кратные i меньше 50.

Согласно вышеупомянутому математическому утверждению, у нас есть все не простые числа до 50. Это верно, потому что мы исчерпываем все простые факторы <= sqrt (50). </p>

Answer 5

Петли - это, в основном, Сито Эратхостенов , но вместо удаления чисел они сохраняют их.

В Сите Эратхостенов вы удаляете кратные "известных"штрихи».Наиболее эффективный способ сделать это, получив простое число p, удалить число p*p, затем p*(p+1) и т. Д., Пока не достигнете предела и продолжить со следующим простым числом q и начать q*q.

Понимание списка - небольшая вариация этого.Вы можете заменить i*2 на i*i и по-прежнему получать те же числа (хотя и с меньшим количеством повторений).

В Сите Эратхостена вы обычно удаляете все четные числа, кроме 2, а затем используете 2*i как шаг диапазона, так как вам нужно учитывать нечетные числа для простоты.Очевидно, что это не так, если вы хотите получить все не простые числа, чтобы «оптимизация» не работала.