Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^3: a close prime number

by Limbic~Region (Chancellor)
on Feb 15, 2005 at 22:32 UTC ( [id://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

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (5)
As of 2024-03-28 08:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found