Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^4: Find prime number between 1 to 1000000

by tilly (Archbishop)
on Jan 24, 2011 at 05:46 UTC ( [id://883854]=note: print w/replies, xml ) Need Help??


in reply to Re^3: Find prime number between 1 to 1000000
in thread Find prime number between 1 to 1000000

No, merlyn was fast because of clever bit-twiddling. Not a good algorithm.

The simple optimization of special casing 2 will result in doubling the speed of his algorithm.

Just to demonstrate this to you, here is the prime generating code that I use for Project Euler problems:

my @primes = (2, 3, 5, 7, 11); # None have been tested sub more_primes { # This adds to the list of primes until it reaches $max # or the square of the largest current prime (assumed odd) my $base = shift || $primes[-1]+1; my $max = shift || $base + 10_000; my $square = $primes[-1] * $primes[-1]; $max = $square if $square < $max; # Determine what to find prime +s to $base++ unless $base % 2; # Make the base odd $max-- if $max %2; # Make the max odd $max = ($max - $base)/2; # Make $max into a count of od +ds return if $max < 0; # Sanity check my $more = ""; # Initialize vector of 0's for + the # odd numbers in our range shift @primes; # Remove 2 foreach my $p (@primes) { my $start; if ($base < $p * $p) { $start = ($p * $p - $base)/2; # Start at the square if ($max < $start) { # Rest of primes don't matter! last; } } else { # Start at first odd it divide +s $start = $base % $p; # Find remainder $start = $p - $start if $start; # Distance to first thing it d +ivides $start += $p if $start %2; # Distance to first odd it div +ides $start = $start/2; # Reindex for counting over od +d! } for (my $i = $start; $i <= $max; $i += $p) { vec($more, $i, 1) = 1; } } unshift @primes, 2; # Replace 2 # Read off list of primes push @primes, map {$_ + $_ + $base} grep {vec($more, $_, 1) == 0} 0. +.$max; } sub ith_prime { my $i = shift; while ($i > $#primes) { more_primes(); } return $primes[$i]; } sub prime_iterator { my $i = -1; return sub { $i++; if ($i > $#primes) { more_primes(); } return $primes[$i]; }; }
And an example of some code using this:
my $iter = prime_iterator(); my $count = 0; $count++ while $iter->() < 1000000; print $count;
On my laptop my code runs in 0.585s while merlyn's code runs in 1.188s.

Note that I could make this code a third faster by special casing 3. But I haven't done this because the prime generating code has never yet been a bottleneck for me. I can generate all of the primes up to 50,000,000 in 33.932s.

However if you need to generate primes *very* quickly, look up http://cr.yp.to/primegen.html. It bit twiddles better than merlyn, uses a better algorithm and is written in C for massively greater efficiency. Seriously, piping input from this program is much, much faster than anything you can do in Perl.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://883854]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2024-03-19 02:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found