- Hour 3: Controlling the Program's Flow
- The if Statement
- Looping
- Other Flow Control Tools
- Exercise: Finding Primes
- Summary
- Q&A
- Workshop
Exercise: Finding Primes
What computer language primer would be complete without this little gem? In this exercise, you will examine a small program to find and print prime numbers. Prime numbers are divisible only by 1 and themselves; for example, 2 is prime, 3 is prime, 4 is not (because it is divisible by 1, 4, and 2), and so on. The list of primes is infinite, and they take a lot of computer power to find.
Using your text editor, type the program from Listing 3.3 and save it as Primes. Do not type in the line numbers. Make the program executable according to the instructions you learned in Hour 1.
When you're done, try running the program by typing the following at a command line:
perl -w Primes
Listing 3.3 The Complete Source for Primes
1: #!/usr/bin/perl -w
2:
3: $maxprimes=20; # Stop when you've found this many
4: $value=1;
5: $count=0;
6: while($count < $maxprimes) {
7: $value++;
8: $composite=0;
9: OUTER: for ($i=2; $i<$value; $i++) {
10: for($j=$i; $j<$value; $j++) {
11: if (($j*$i)==$value) {
12: $composite=1;
13: last OUTER;
14: }
15: }
16: }
17: if (! $composite) {
18: $count++;
19: print "$value is prime\n";
20: }
21: }
Line 1: This line contains the path to the interpreter (you can change it so that it's appropriate to your system) and the -w switch. Always have warnings enabled!
Line 3: $maxprimes is the maximum number of primes you want to find.
Line 4: $value is the value you're going to test for primeness.
Line 5: $count is the number of primes so far.
Line 6: The while loop continues as long as the program hasn't found enough primes.
Line 7: $value is incremented, so the first number to be checked for prime quality is 2.
Line 8: $composite is a flag used in the for loops to indicate that the number found is composite, not prime.
Lines 9-10: The for loops iterate through all the possible factors of $value. If $value were 4, the loops would produce 2 and 2, 2 and 3, 3 and 2, 3 and 3.
Lines 11-14: The values of $i and $j are multiplied together; if the product is $value, then $value is composite. The flag $composite is set, and both for loops are exited.
Lines 17-20: After the for loops, the $composite flag is checked. If it's false, the number is prime. These lines then print a message and increment the counter.
NOTE
The algorithm used here to find primes isn't particularly speedy or efficient—but it makes for a good demonstration of looping. A better method can be found in a good book on numerical algorithms.