Tom's Guide | Tom's Hardware | Tom's Games
 |
 |
 |
This is what I have so far
#!/usr/bin/perl -w
$n=$ARGV[0];
if (sqrt $n){
printf("$n is prime\n");
}
die "Supply exactly one argument\n" unless @ARGV == 1;
die "Supply a positive integer\n" unless $ARGV[0] =~ /^\d+$/;
0 
Is this a homework assignment?
I think you want @ARGV[0], not $ARGV[0] to get the first command line value.
Google for "Sieve of Eratosthenes" to get a classical prime number generator. Basically, it starts with an array of numbers 1 to $n. After 2, cross off every even number. 3 is still there so it is prime, cross off every multiple of 3. And so on. At the end, if $n has survived, it's prime. Very fast, but fairly bulky (although you could use a single bit for each number).
Another way to attack it is to try dividing $n by 2, by 3, etc. all the way up through sqrt($n). If no even division found, it's prime. The tricky part is to reduce the number of test divisions by eliminating multiples of lower primes. E.g., once you've eliminated 3 as a divisor, there's no point in trying any of its multiples (6, 9, 12,...). If $n is not terribly large, you may just want to go ahead and divide by every odd number larger than 2 (3, 5, 7,...) and see if you get any even divisions. It might be worthwhile, especially if $n might be very large, to keep a list of primes you've found already (less than sqrt($n)) and first testing if the divisor under consideration is a multiple of a prime already found and can be eliminated. E.g., no point in dividing by 15, because we already checked for 3 (not to mention 5). Of course, if sqrt($n) is an integer, $n is a square and not a prime. The chief problem with this approach is that you're doing lots and lots of expensive divisions, while the Sieve just advances through a list of possible divisors (which could be single bits 1=still alive, 0=eliminated).
Good luck with your homework assignment! ;-)
0  |
 |
 |
This post is quite old and has been locked from receiving new replies. Please create a new posting instead.
| Ads by Google |
