Как найти простые числа в диапазоне?

Question

[Oli]

Здравствуйте! Вы не могли бы сказать, как с помощью решета Эратосфена можно найти простые числа в диапазоне?

def sieve(n):
    prime = list(range(n + 1))
    prime[1] = 0
    i = 2
    while i * i <= n:
        if prime[i]:
            j = i * i
            while j <= n:
                prime[j] = 0
                j += i
        i += 1
    return prime

Answer 1

[Vindicar]

Решето Эратосфена предполагает удаление элементов, кратных очередному простому числу.
Т.е. обработали 2 - вычеркиваем каждый 2й элемент. Обработали 3 - каждый третий, и так далее.
Отсюда получаем следующее.
У нас есть исходный список элементов.
numbers = list(range(2, n+1))
На каждом шаге, когда мы проверяем число k, мы выкидываем все числа, кратные k, кроме самого k.

numbers = [ x for x in numbers if x % k != 0 or x == k]

А как мы выбираем k? Просто идём по списку чисел от начала. Все элементы в начале списка всегда будут простыми, так как 2 - простое, а все последующие составные элементы будут выкинуты на одной из итераций

i = 0
while i < len(numbers):
  k = numbers[i]
  numbers = [ x for x in numbers if x % k != 0 or x == k ]
  i += 1