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

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

oldrob
Novice

Feb 14, 2013, 5:21 AM

Post #1 of 7 (924 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 (918 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 (909 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 (906 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 (902 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 (897 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
Enthusiast / Moderator

Feb 14, 2013, 3:52 PM

Post #7 of 7 (894 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.

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0