Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re^3: a close prime number

by Limbic~Region (Chancellor)
on Feb 15, 2005 at 22:32 UTC ( #431364=note: print w/ replies, xml ) Need Help??


in reply to Re^2: a close prime number
in thread a close prime number

gam3,
I have added several improvements:

  • Cache is now persistent
  • Primeness is determined in C
  • The 2 4 trick is used in checking near numbers also
  • An iterator is used in lieu of a stack
#!/usr/bin/perl use strict; use warnings; use DBM::Deep; use Inline C =>; my $prime = DBM::Deep->new( 'primes.db' ); #$prime->{is}{$_} = 1 for (2, 3, 5, 7, 11, 13, 17, 19, 23); # 1st run +only my $next = find_near_primes(10000 => 100); while ( my $p = $next->() ) { print "$p\n"; } sub find_near_primes { my ($num, $tot) = @_; my ($below, $above, $up, $down); my $by_2_4 = sub { my $n = shift; return sub { return $n = $n == 2 + ? 4 : 2 } }; my $dir = -1; return sub { return () if ! $tot--; $dir *= -1; if ( $num ) { $num = $num - $num % 3; $num += not ($num % 2) ? -1 : 2; ($below, $above, $num) = ($num, $num, undef); ($up, $down) = ($by_2_4->( 4 ), $by_2_4->( 2 )); $below -= $down->(); } if ( $dir == 1 || $below < 5 ) { if ( ! $prime->{is}{$above} ) { $above += $up->() while $prime->{not}{$above}; while ( ! is_prime( $above ) ) { $prime->{not}{$above} = 1; $above += $up->() while $prime->{not}{$above}; last if $prime->{is}{$above}; } $prime->{is}{$above} = 1; } my $p = $above; $above += $up->() and return $p; } else { if ( ! $prime->{is}{$below} ) { $below -= $down->() while $prime->{not}{$below}; while ( ! is_prime( $below ) ) { $prime->{not}{$below} = 1; $below -= $down->() while $prime->{not}{$below}; last if $prime->{is}{$below}; } $prime->{is}{$below} = 1; } my $p = $below; $below -= $down->() and return $p; } }; } __END__ __C__ #include <math.h> short is_prime (unsigned long num) { unsigned long i = 5; unsigned long j = sqrt( num ); while ( i <= j ) { if ( num % i == 0 ) return 0; i += 2; if ( num % i == 0 ) return 0; i += 4; } return 1; }
Tag - you're it!

Cheers - L~R


Comment on Re^3: a close prime number
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (17)
As of 2015-07-28 16:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (258 votes), past polls