Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: a close prime number

by TedPride (Priest)
on Feb 11, 2005 at 22:03 UTC ( #430317=note: print w/ replies, xml ) Need Help??


in reply to a close prime number

use strict; use warnings; print nearPrime(100000); sub nearPrime { my $num = shift; $_ = 0; return $num if isPrime($num); while (1) { $_++; return ($num - $_) if isPrime($num - $_); return ($num + $_) if isPrime($num + $_); } } BEGIN { my @primes = (2); my $max = 2; sub isPrime { my $num = shift; my $root = int sqrt $num; if ($root > $max) { for (($max+1)..$root) { push(@primes, $_) if isPrime($_); } $max = $root; } for (@primes) { return 0 if ($num % $_ == 0); } return 1; } }


Comment on Re: a close prime number
Download Code
Re^2: a close prime number
by Roy Johnson (Monsignor) on Feb 11, 2005 at 22:27 UTC
    I think yours is working a little harder than necessary. (Update: I didn't recognize the cache.) Also note that you ought to localize $_ if you're going to use it where Perl isn't automatically localizing it.
    for (10,15,20831323,99,100) { print "$_: ", nearPrime($_), "\n"; } sub nearPrime { my $num = shift; local $_ = 0; # otherwise tries to modify for loop var above return $num if isPrime($num); while (1) { $_++; return ($num - $_) if isPrime($num - $_); return ($num + $_) if isPrime($num + $_); } } ...
    An alternative nearPrime sub:
    sub nearPrime { my $num = shift; my $sign = 1; return $num if isPrime($num); for (0..$num) { $num += $sign * $_; return $num if isPrime($num); $sign = -$sign; } }
    And this isPrime does a little less work by checking only odd numbers:
    BEGIN { my @primes = (2, 3); my $max = 3; sub isPrime { my $num = shift; my $root = int sqrt $num; while ($max <= $root) { $max += 2; push(@primes, $max) if isPrime($max); } for (@primes) { last if $_ > $root; return 0 if ($num % $_ == 0); } return 1; } }

    Caution: Contents may have been coded under pressure.
Re^2: a close prime number
by Roy Johnson (Monsignor) on Feb 11, 2005 at 23:34 UTC
    One other bug:
    for (@primes) { last if $_ > $root; # If you have checked bigger primes, +you don't want to go through all of them! print("$_ divides $num\n"), return 0 if ($num % $_ == 0); }

    Caution: Contents may have been coded under pressure.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (14)
As of 2014-07-23 12:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (140 votes), past polls