Anonymous user
Primality by trial division: Difference between revisions
→{{header|Perl}}: Add small wheel version, and comment about regex
m (Revert extra text added to description in one of the previous edits) |
(→{{header|Perl}}: Add small wheel version, and comment about regex) |
||
Line 1,632:
=={{header|Perl}}==
A
<lang perl>sub prime { my $n = shift || $_;
$n % $_ or return for 2 .. sqrt $n;
Line 1,639:
print join(', ' => grep prime, 1..100), "\n";</lang>
===Excluding multiples of 2 and 3===
One of many ways of writing trial division using a mod-6 wheel. Almost 2x faster than the simple method shown earlier.
<lang perl>sub isprime {
my $n = shift;
return ($n >= 2) if $n < 4;
return unless $n % 2 && $n % 3;
my $sqrtn = int(sqrt($n));
for (my $i = 5; $i <= $sqrtn; $i += 6) {
return unless $n % $i && $n % ($i+2);
}
1;
}
my $s = 0;
$s += !!isprime($_) for 1..100000;
print "Pi(100,000) = $s\n";</lang>
===By Regular Expression===
JAPH by Abigail 1999 [http://diswww.mit.edu/bloom-picayune.mit.edu/perl/12606] in conference slides 2000 [http://www.perlmonks.org/?node_id=21580].
While this is extremely clever and often used for [[wp:Code golf|Code golf]], it should never be used for real work (it is extremely slow and uses lots of memory).
<lang perl>sub isprime {
('1' x shift) !~ /^1?$|^(11+?)\1+$/
}
print join(', ', grep(isprime($_), 0..39)), "\n";</lang>
| |||