CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner:
beginner prime number script

 



oldrob
Novice

Feb 14, 2013, 5:21 AM

Post #1 of 7 (1119 views)
beginner prime number script Can't Post

Hello all,

Im new to programming in general and am attempting to code a program to find the prime numbers for a given range. Please see my (unfinished) code below. Perl returns an error 'illegal modulus zero at line 14 which suggests that $primes[$m] is zero (indeed this part of the code works if i just replace this variable with an integer. Can anyone point out where I am going wrong? much help appreciated.


Code
 
#!/usr/bin/perl
use warnings;

#code to determine primes

print "find primes between 2 and ?\n";
$upper = <STDIN>;

@range = (3..$upper);
@primes = (2);

foreach my $n (@range){ #for every entry of @range, $n)
foreach my $m (@primes) { #for every number in @primes
if ($range[$n] % $primes[$m] == 0){
} #if $n modulo prime is zero
#do nothing
else {print "did we get here at least?"}#{@primes = (@primes, $n)}; #otherwise add $n to the list of primes
};
};

print "@primes\n";



FishMonger
Veteran / Moderator

Feb 14, 2013, 6:44 AM

Post #2 of 7 (1113 views)
Re: [oldrob] beginner prime number script [In reply to] Can't Post

@primes is initialized with a single element and never altered. So, when you then reference a non existent array element (which is evaluated as undef or 0 depending on context), you receive the "illegal modulus zero" error.


BillKSmith
Veteran

Feb 14, 2013, 11:03 AM

Post #3 of 7 (1104 views)
Re: [oldrob] beginner prime number script [In reply to] Can't Post

It is easier to find prime numbers by eliminating the non-primes. The following code finds all primes less than or equal to the number specified on the command line (default = 53). I could add code to reduce redundant processing, but that would obscure the concept. Note that the only arithmetic used is integer addition.

Code
use strict; 
use warnings;
use integer;
my @candidates;
$#candidates = $ARGV[0] // 53;
@candidates = 0..$#candidates; # Init all candidates to prime
for my $i (2 .. $#candidates) { # Assume that 2 is prime
my $j = $i;
while ($j <= ($#candidates-$i)) {
$j += $i;
$candidates[$j] = 0; # All multiples of $i are non-prime
}
}
my @primes = grep {$_} @candidates;
print "@primes\n";

Good Luck,
Bill


FishMonger
Veteran / Moderator

Feb 14, 2013, 12:35 PM

Post #4 of 7 (1101 views)
Re: [BillKSmith] beginner prime number script [In reply to] Can't Post

As long as we're providing the answer to someones homework assignment, we might as well provide a more efficient module solution.


Code
#!/usr/bin/perl 

use strict;
use warnings;
use Math::Prime::XS qw(primes);

my $upper_limit = shift || 100;
print "$_\n" for primes( $upper_limit );


c:\testing>primes.pl
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97


(This post was edited by FishMonger on Feb 14, 2013, 12:37 PM)


BillKSmith
Veteran

Feb 14, 2013, 1:31 PM

Post #5 of 7 (1097 views)
Re: [FishMonger] beginner prime number script [In reply to] Can't Post

Sorry, I did not consider my posted code a complete answer because of the efficiency issues and because it does not address the lower end of the range, but I do see what you mean.
Good Luck,
Bill


oldrob
Novice

Feb 14, 2013, 2:20 PM

Post #6 of 7 (1092 views)
Re: [BillKSmith] beginner prime number script [In reply to] Can't Post

Hello all, many thanks for this - I know its probably not the most efficient coding but im just getting to grips with perl. Im trying to understand the problem with my syntax before moving onto the more complicated concepts. There's always more than one way to do it right?


Quote
As long as we're providing the answer to someones homework assignment, we might as well provide a more efficient module solution.


actually a post-doc doing chemistry - no more homework for me!


Laurent_R
Veteran / Moderator

Feb 14, 2013, 3:52 PM

Post #7 of 7 (1089 views)
Re: [oldrob] beginner prime number script [In reply to] Can't Post

OK, to many of us, "looking for a list of the first 100 prime numbers" really sounds like homework as it is such a classical assignment in general programming, basic algorithmic theory and (whatever specific) language learning, that we tend to react this way. I remember distinctly having homework assignments to write a Pascal and a C programs for generating the first 1,000,000 prime numbers (or maybe, all the prime numbers below 1,000,000, I am not sure). I loved it and I made numerous successive performance improvements (such as discarding even numbers above 2 before doing any calculations, and then aslo discarding multiples of 3, 5 and 10, etc.). The most efficient improvement, I remember that vividly althouh it was more than 20 years ago, was to store the primes that I found in an array, so that I would check for divisibility of new numbers only against primes in my array (up to square root of the number). I also remember that I got the best possible mark on this assignment. Son to make a long story short, looking for pirme numbers awfully sounds like a homework assignment.

But I must say that when I decided that I wanted to learn Perl, and this had nothing to do with my studies (it was years later), I also tried, among many other things, to find prime numbers. So that I understand what you are trying to do here. (And I also dit it in other languages).

In terms of algorithmics, there are two basic ways:
- check, for each number in a list, if it can be divided by a smaller number (the performance improvement being basically: if it can be divided by another prime number smaller than square root of that number);
- Eratosthene's sieve: prepare a list of numbers, iterate over a list of prime numbers, and cross out in the first list all numbers that are multiples of the primes.

The most efficient method is likely to be a combination of both methods. For instance, the method I used for the assignment described above was essentially based on the first one, but the idea of skipping immediately even numbers or multiples of 3, 5 and 10 is closer to an application of Erathosthene's sieve method.

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives