Курс языка программирования Raku / Приложение 🆕 / Собираем всё вместе / Смешанные мини-проекты / Exercises / Решето Эратосфена

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

Вот один из возможных вариантов решения задачи.

Код

my $limit = 30;
my %composite;

for 2 .. $limit -> $i {
    next if %composite{$i};
    for ($i², $i² + $i ... $limit) -> $multiple {
        %composite{$multiple} = True;
    }
}

say (2..$limit).grep({ !%composite{$_} });

🦋 Исходный код можно найти в файле sieve.raku.

Вывод

(2 3 5 7 11 13 17 19 23 29)

Комментарии

1. Вместо списка флагов %composite запоминает, какие числа уже вычеркнуты. Число, которого в нём ещё нет к моменту, когда доходит его черёд, является простым.

2. Для каждого простого $i его кратные порождаются последовательностью $i², $i² + $i ... $limit и помечаются составными. Начало с $i² пропускает кратные, уже обработанные меньшими простыми.

3. Это одна последовательность, а не заголовок цикла for в стиле C. Оператор ... берёт первые два значения, вычисляет шаг между ними и продолжает до предела. Для $i, равного 3, это означает начало с 9, затем 12, то есть шаг 3, и цикл проходит весь список:

   my $i = 3;
   say ($i², $i² + $i ... 30); # (9 12 15 18 21 24 27 30)

   Так что for получает один список для обхода — 9, 12, 15, …, — а не три отдельные части заголовка.

4. $i² возводит число в квадрат с помощью надстрочного знака Unicode. Raku принимает все три записи — $i * $i, $i ** 2 и $i², — они вычисляют в точности одно и то же значение, поэтому выбирайте ту, что читается вам лучше. Надстрочные цифры (², ³, …) — обычные символы, которые можно набрать или вставить прямо в исходный код.

Навигация по курсу

← Решето Эратосфена   |   Оценки из строк CSV →