Sieve of Pritchard: Difference between revisions
Added Perl
m (→{{header|J}}: bugfix for pr 1000) |
SqrtNegInf (talk | contribs) (Added Perl) |
||
Line 280:
up to 1000000, added 186825, removed 108494, prime count 78498
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl" line>use v5.36;
use List::Util 'min';
my($limit, $maxS, $length, $p, @s) = (150, 1, 2, 3);
sub next_($w) { $s[$w-1] }
sub prev_($w) { $s[$w-2] }
sub append($w) {
$s[$maxS-1] = $w;
$s[$w-2] = $maxS;
$maxS = $w;
}
sub delete_multiples_of($p) {
my $f = $p;
while ($p*$f <= $length) { $f = next_ $f }
while ( $f > 1 ) { $f = prev_ $f; delete_pf($p*$f) }
}
sub delete_pf($pf) {
my($temp1, $temp2) = ($s[$pf-2], $s[$pf-1]);
$s[ $temp1-1 ] = $temp2;
$s[($temp2-2)%@s] = $temp1;
}
sub extend_to($n) {
my($w, $x) = (1, $length+1);
while ($x <= $n) {
append $x;
$w = next_ $w;
$x = $length + $w;
}
$length = $n;
append $limit+2 if $length == $limit
}
do {
extend_to min $p*$length, $limit if $length < $limit;
delete_multiples_of $p;
$p = next_ 1;
extend_to $limit if $length < $limit
} until $p*$p > $limit;
my @primes = 2;
for (my $p = 3; $p <= $limit; $p = next_ $p) { push @primes, $p }
say "@primes";</syntaxhighlight>
{{out}}
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149</pre>
=={{header|Phix}}==
| |||