|
Here's some of the perl one I did to knock the rust off... I got a java version as well both implment the Eratosthenes Seive and stops at the sqrt... it works pretty darn quick...
<code>
#!/usr/bin/perl -w
my @prime_list = ();
my @sieve_list = ();
my $end = $ARGV[0];
my $stopping_point = sqrt ($end);
my $debug = 0;
if ($end < 2)
{
*print "Must enter a integer > 1";
*exit 1;
}
print "Finding all primes from 2 to $end \n";
print "\tand stopping the sieve at $stopping_point\n";
# build inital sieve list
for (my $i = 2; $i<=$end; $i++)
{
*push (@sieve_list,$i);
}
*
# ok now we should have the list built up we will loop
# let's prime the pump
my $prime = $sieve_list[0];
my $iterations = 0;
while ( $prime <= $stopping_point )
{
*$iterations += 1;
*# add the prime to the prime list
*push (@prime_list,$prime);
*# strike off the stuff that's not
*my @temp_sieve = ();
*foreach my $test (@sieve_list)
*{
**if ($test == $sieve_list[0])
**{
***next;
**}
**
**# if the number is devisible by the prime, drop it
**$mod = $test % $prime;
**if ($mod)
**{
***push (@temp_sieve,$test);
**}
*}
*@sieve_list = @temp_sieve;
*# get the next prime
*$prime = $sieve_list[0];
}
# add the rest
foreach $prime (@sieve_list)
{
*push (@prime_list,$prime);
}
print "Primes: \n\t";
my $lines = 0;
foreach $prime (@prime_list)
{
*print "$prime";
*if ($lines == 10)
*{
**print "\n\t";
**$lines = 0;
*}
*else
*{
**print "\t";
**$lines += 1;
*}
}
#print "\n";
#print "# of iterations is $iterations \n";
</code>
I will post the java one when I get a chance... they are both not that pretty but they are darned fast..
|