Sieve of Eratosthenes · Решето Эратосфена
Sieve of Eratosthenes
The Greek mathematician Eratosthenes found primes without dividing anything: write down the numbers, then cross out the multiples of each prime.
[True] * (n + 1) makes a list of n + 1 True values, one for each number from 0 to n. Mark 0 and 1 as not prime. Then, for each p still marked True, set every multiple of p from p * p onwards to False. The numbers still marked True at the end are the primes.
Решето Эратосфена
Греческий математик Эратосфен находил простые числа без деления: запишите все числа, затем зачеркните кратные каждому простому числу.
[True] * (n + 1) создаёт список из n + 1 значений типа True, по одному для каждого числа от 0 до n. Отметьте 0 и 1 как непростые. Затем для каждого p, всё ещё помеченного как True, установите каждое кратное p начиная с p * p в состояние False. Числа, оставшиеся помеченными как True в конце, являются простыми.
Write primes_up_to(n) that returns every prime number from 2 to n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · Напишите primes_up_to(n), которая возвращает все простые числа от ⟨2⟩ до ⟨n⟩ в порядке возрастания, используя решето Эратосфена. ⟨primes_up_to(10)⟩ равно ⟨[2, 3, 5, 7]⟩.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.