Перейти к содержанию

Sieve of Eratosthenes

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

Греческий математик Эратосфен находил простые числа без деления: запишите все числа, затем зачеркните кратные каждому простому числу.

[True] * (n + 1) создаёт список из n + 1 значений типа True, по одному для каждого числа от 0 до n. Отметьте 0 и 1 как непростые. Затем для каждого p, всё ещё помеченного как True, установите каждое кратное p начиная с p * p в состояние False. Числа, оставшиеся помеченными как True в конце, являются простыми.

Войти или создать аккаунт

IGCSE, A-Level & AP