Prime number generation, and range operator

dReKurCe has asked for the wisdom of the Perl Monks concerning the following question:

Greetings Monks, The following is a script for generating prime numbers. I hope that it works because at this point all of my hardware, except my trusty T1200 text processor is down. This is a terrible situation because my perl skills are rusting. None the less, I have uploaded this at a public access terminal and if any monk cares to email the output to neutrin0@cyberspace.org I would be inspired. Further more, I am curious about the nature of the range operator. I have utilized it's two incarnations in the following:

#! /usr/bin/perl

use Math::BigInt ':constant';

my $i;
my $target;
my $flta;
my $fltb;
my $base;
my $exp;

my $i=1;
for $target(1...560){
flt($target);
print "$target is prime number $i";
if ($i==560){print "From $target and greater are the appearance of Car
+michael numbers,other primality tests are required.";}

sub flt{
$target=shift @_;
$exp=$target -1;
PRIMALITY: 
for $base(1..$exp){
$flta=$base**$exp;
$fltb=$flta%$target;
if ($fltb==1){
next PRIMALITY;
}else{
last}
$i=$i+1;
return $target;
}
[download]

Retitled by davido from 'Primality'.

Comment on Prime number generation, and range operator Download Code

Replies are listed 'Best First'.
Re: Prime number generation, and range operator by jdalbec (Deacon) on Jan 29, 2005 at 04:37 UTC
I took the liberty of running your code through `perltidy` which pointed out that you're missing two right braces (`}`). I fixed that and modified `flt()` to return `undef` if the number is not prime and made the print statement conditional on the return value. I changed the condition on the print statement about Carmichael numbers to `$target==560` since `$i` is never going to reach 560. If you Google "strong probable primes" you'll find out about a modification of the FLT test where every composite number fails the test for at least half the exponents. There's no equivalent to Carmichael numbers for this modified test. I added a `"\n"` to each of your print statements. If you don't add newlines, your print statements will be jammed together on one line and you won't see any output until Perl's output buffer fills up or the program ends. Your method of computing powers modulo a number is extremely inefficient. You should look into better algorithms for doing that. For extra credit, implement one of the new deterministic polynomial-time algorithms for primality testing. :-) #! /usr/bin/perl use Math::BigInt ':constant'; my $i; my $target; my $flta; my $fltb; my $base; my $exp; my $i = -1; for $target ( 1 ... 560 ) { print "$target is prime number $i\n" if flt($target); if ( $target == 560 ) { print "From $target and greater are the appearance of Carmichael numbers,oth +er primality tests are required.\n"; } } sub flt { $target = shift @_; $exp = $target - 1; PRIMALITY: for $base ( 1 .. $exp ) { $flta = $base**$exp; $fltb = $flta % $target; if ( $fltb == 1 ) { next PRIMALITY; } else { return; } } $i = $i + 1; return $target; } [download] Now it outputs: `1 is prime number 0 2 is prime number 1 3 is prime number 2 5 is prime number 3 7 is prime number 4 11 is prime number 5 ...` [download]	[reply] [d/l] [select]
Re: Prime number generation, and range operator by nerfherder (Monk) on Jan 28, 2005 at 23:14 UTC
Well, it needs some help... No time to test at the moment, but I'd like to mention that this wheel has already been invented: http://search.cpan.org/~cwest/ppt-0.14/src/primes/primes *Update:* After reading jdalbec's brilliantly concise reply, I'd like to share a link to some wisdom/magic on this topic, located exactly where you'd expect: http://www.stonehenge.com/merlyn/UnixReview/col26.html	[reply]
Re: Prime number generation, and range operator by ambrus (Abbot) on Jan 29, 2005 at 10:44 UTC
There's a bmodpow method in Math::BigInt, that calculates a power of a number over a modulus. (I think this would still be a very slow primality test that way.) Update: or you could leave M::BI out altogether and use a hand-rolled modpow function, such as `sub modpow { my($b, $p, $m) = @_; my $r = 1; for (;;) { $p & 1 and $r += ($r * $b) % $m; 0 < ($p >>= 1) or last; $b = ($b * $b) % $m; } $r; +} $s = 0; for $n (2..1000) { modpow($_, $n - 1, $n) != 1 and goto G for +2 .. $n - 1; print $n, " appears to be prime ", ++$s, "\n"; G: }` [download] Update: or, without the goto: `sub modpow { my($b, $p, $m) = @_; my $r = 1; for (;;) { $p & 1 and $r += ($r * $b) % $m; 0 < ($p >>= 1) or last; $b = ($b * $b) % $m; } $r; +} $s = 0; G: for $n (2..1000) { modpow($_, $n - 1, $n) != 1 and next G for 2 .. +$n - 1; print $n, " is prime number ", ++$s, "\n"; }` [download]	[reply] [d/l] [select]


Perl-Sensitive Sunglasses
	PerlMonks