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

Используя алгоритм «Решето Эратосфена», найдите все простые числа до заданного числа N.

n = int(input())

# заполняем список числами от 0 до n
a = []
for i in range(n + 1):
    a.append(i)

# Вторым элементом является единица,
# которую не считают простым числом
# забиваем ее нулем.
a[1] = 0

# начинаем с 3-го элемента
i = 2
while i <= n:
    # Если значение ячейки до этого
    # не было обнулено, в этой ячейке
    # содержится простое число.
    if a[i] != 0:
        # Первое кратное ему будет
        # в два раза больше.
        j = i + i
        while j <= n:
            # Это число составное,
            # поэтому заменяем его нулем.
            a[j] = 0
            # Переходим к следующему числу,
            # которое кратно i (оно на i больше).
            j = j + i
    i += 1

# Превращая список во множество,
# избавляемся от всех нулей кроме одного.
a = set(a)
# удаляем ноль
a.remove(0)
print(a)




Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: