Course of Raku / Addendum 🆕 / Bringing it together / Mixed mini-projects / Exercises / Sieve of Eratosthenes

Solution: Sieve of Eratosthenes

Here is a possible solution to the task.

Code

my $limit = 30;
my %composite;

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

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

🦋 You can find the source code in the file sieve.raku.

Output

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

Comments

Instead of a list of flags, %composite remembers which numbers have been crossed out. A number still missing from it when its turn comes is prime.
For each prime $i, its multiples are generated as the sequence $i*$i, $i*$i + $i ... $limit and marked composite. Starting at $i*$i skips multiples already handled by smaller primes.

← Sieve of Eratosthenes | Scores from CSV lines →