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;
}
}

Replies are listed 'Best First'.
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.

Create A New User
Node Status?
node history
Node Type: note [id://430317]
help
Chatterbox?
 [atcroft]: PriNet: %hash = ();? or foreach my \$k ( keys %hash ) { delete \$hash{\$k}; }?

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (2)
As of 2017-06-28 02:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (619 votes). Check out past polls.