The sieve of Eratosthenes: you've been there; done that; have the T-shirt. The sieve of Eratosthenes was ancient history when Euclid was a schoolboy. You are ready for something less than 3000 years old. You are ready for The sieve of Sundaram.

Starting with the ordered set of +ve integers, mark every third starting at 4 (4;7;10...).

Step through the set and if the value is not marked output 2*n+1. So from 1 to 4 output 3 5 7.

4 is marked so skip for 5 and 6 output 11 and 13.

7 is marked, so no output but now also mark every fifth starting at 12 (12;17;22...)

as per to 10 and now mark every seventh starting at 17 (17;24;31....)

as per for every further third element (13;16;19...) mark every (9th;11th;13th;...) element.

The output will be the ordered set of odd primes.

Using your function find and output the first 100 and the millionth Sundaram prime.

The faithless amongst you may compare the results with those generated by The sieve of Eratosthenes.

References

 The article on Wikipedia.


use strict;
use warnings;
use feature 'say';
 
my @sieve;
my $nth = 1_000_000;
my $k = 2.4 * $nth * log($nth) / 2;
 
$sieve[$k] = 0;
for my $i (1 .. $k) {
    my $j = $i;
    while ((my $l = $i + $j + 2 * $i * $j) < $k) {
        $sieve[$l] = 1;
        $j++
    }
}
 
$sieve[0] = 1;
my @S = (grep { $_ } map { ! $sieve[$_] and 1+$_*2 } 0..@sieve)[0..99];
say "First 100 Sundaram primes:\n" .
    (sprintf "@{['%5d' x 100]}", @S) =~ s/(.{50})/$1\n/gr;
 
my ($count, $index);
for (@sieve) {
    $count += !$_;
    (say "One millionth: " . (1+2*$index)) and last if $count == $nth;
    ++$index;
}