Re: How can I make my prime number generator better?
- From: Abigail <abigail@xxxxxxxxxx>
- Date: 23 Mar 2007 15:32:10 GMT
nikolas.britton@xxxxxxxxx (nikolas.britton@xxxxxxxxx) wrote on MMMMCMLII
September MCMXCIII in <URL:news:1174610848.316977.94170@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>:
@@ How can I improve my code?... faster, better style, proper programming
@@ techniques, better algorithm? Thanks!
A better algorith beats everything else.
If you want to generate prime numbers starting from 1, sieves are your
best option. They have been your best option since antiquity.
Here's an example of a sieve:
#!/opt/perl/bin/perl -l
# A sieve based on base 6. Only possible primes are those numbers p
# for which p mod 6 == 1, or p mod 6 == 5.
#
# Let n = 6 * k + l (0 <= l < 6). Then the bit b associated with n is
# b = 2 * k + [undef, 0, undef, undef, undef, 1] -> [l]
# In reverse, given a bit b, the corresponding number n is
# n = 6 * int (b / 2) + [1, 5] -> [b % 2].
use strict;
use warnings 'all';
sub scrub ($);
sub findnext ($);
my $max = $ARGV [0] || 1000;
my @PRIMES = (2, 3);
my $BASE = 6; # LCM of @PRIMES.
my $BITS_BASE = 2;
my $BITS_BYTE = 8;
my $bits = $BITS_BASE * int ($max / $BASE) + ($max % $BASE ? $BITS_BASE : 0);
my $bytes = int ($bits / $BITS_BYTE) + ($bits % $BITS_BYTE ? 1 : 0);
my $sieve = eval qq !"\xFF" x $bytes!; # Half the memory usuage.
# Numbers less than the base are special.
foreach my $prime (@PRIMES) {
print $prime
}
my $i = 5;
for (; $i && $i <= sqrt ($max); $i = findnext $i) {
print $i;
scrub $i;
}
for (; $i && $i < $max ; $i = findnext $i) {
print $i;
}
exit;
my ($offset1, $offset2);
INIT {
$offset1 = [undef, 0, undef, undef, undef, 1];
$offset2 = [1, 5];
}
# Scrub out all multiples of the given argument. It's easy to see that
# all multiples less than the square already have been crossed out, and
# we only have to scrub out the odd multiples.
sub scrub ($) {
use integer;
my $n = shift;
my $m = $n;
if ($m % 3 == 1) {
my $c = $n * $m;
vec ($sieve, $BITS_BASE * ($c / $BASE) + $offset1 -> [$c % $BASE],
1) = 0;
$m += 4;
}
my $c = $n * $m;
# $b is the bit index in the sieve, $b1 and $b2 are the increments
# in the loop.
my $b = $BITS_BASE * ($c / $BASE) + $offset1 -> [$c % $BASE];
my $b1 = (2 * $n / ($BASE / $BITS_BASE));
my $b2 = (4 * $n / ($BASE / $BITS_BASE));
# Exactly one of $b1, $b2 needs to be incremented by 1,
# depending on the parity of $c.
($c % 6 == 1 ? $b2 : $b1) += 1;
# Make sure we don't go out of range.
my $l = $bits - $b1 - $b2;
# Core loop, we want to minimize work here.
while ($b <= $l) {
vec ($sieve, $b, 1) = 0; $b += $b1;
vec ($sieve, $b, 1) = 0; $b += $b2;
}
# Basically a copy of the previous loop, but with extra checks.
# Checks don't hurt now as this loop is performed only once.
{
last if $b > $bits;
vec ($sieve, $b, 1) = 0; $b += $b1;
last if $b > $bits;
vec ($sieve, $b, 1) = 0; $b += $b2;
}
}
# Find the next prime number after the given number.
sub findnext ($) {
use integer;
my $n = shift;
my $i = $BITS_BASE * ($n / $BASE) + $offset1 -> [$n % $BASE] + 1;
while ($i <= $bits) {
if (vec ($sieve, $i, 1)) {
return $BASE * ($i / $BITS_BASE) + $offset2 -> [$i % $BITS_BASE]
}
$i ++
} undef;
}
__END__
--
print 74.117.115.116.32, 97.110.111.116.104.101.114.32,
80.101.114.108.32, 72.97.99.107.101.114.10;
.
- Follow-Ups:
- Re: How can I make my prime number generator better?
- From: anno4000
- Re: How can I make my prime number generator better?
- From: bugbear
- Re: How can I make my prime number generator better?
- References:
- How can I make my prime number generator better?
- From: nikolas . britton
- How can I make my prime number generator better?
- Prev by Date: Re: How can I make my prime number generator better?
- Next by Date: Re: perl: adding lines and replacing stings
- Previous by thread: Re: How can I make my prime number generator better?
- Next by thread: Re: How can I make my prime number generator better?
- Index(es):
Relevant Pages
|
