This section presents a program that displays the first 50 prime numbers in 5 lines, each containing 10 numbers.
An integer greater than 1 is prime if its only positive divisor is 1 or itself. For example, 2, 3, 5, and 7 are prime numbers, but 4, 6, 8, and 9 are not.
The program can be broken into the following tasks:
- Determine whether a given number is prime.
- For number = 2, 3, 4, 5, 6, . . . , test whether it is prime.
- Count the prime numbers.
- Display each prime number, and display ten numbers per line.
Obviously, you need to write a loop and repeatedly test whether a new number is prime. If the number is prime, increase the count by 1. The count is 0 initially. When it reaches 50, the loop terminates.
Here is the algorithm:
Set the number of prime numbers to be printed as
a constant NUMBER_OF_PRIMES;
Use count to track the number of prime numbers and
set an initial count to 0;
Set an initial number to 2;
while (count < NUMBER_OF_PRIMES)
{
Test whether number is prime;
if number is prime {
Display the prime number and increase the count;
}
Increment number by 1;
}
To test whether a number is prime, check whether it is divisible by 2, 3, 4, up to number/2. If a divisor is found, the number is not a prime. The algorithm can be described as follows:
Use a bool variable isPrime to denote whether
the number is prime; Set isPrime to true initially;
for (int divisor = 2; divisor <= number / 2; divisor++)
{
if (number % divisor == 0)
{
Set isPrime to false Exit the loop;
}
}
The complete program is given in Listing 5.17.
Listing 5.17 PrimeNumber.cpp
1 #include <iostream>
2 #include <iomanip>
3 using namespace std;
4
5 int main()
6 {
7 const int NUMBER_OF_PRIMES = 50; // Number of primes to display
8 const int NUMBER_OF_PRIMES_PER_LINE = 10; // Display 10 per line
9 int count = 0; // Count the number of prime numbers
10 int number = 2; // A number to be tested for primeness
11
12 cout << “The first 50 prime numbers are \n”;
13
14 // Repeatedly find prime numbers
15 while (count < NUMBER_OF_PRIMES)
16 {
17 // Assume the number is prime
18 bool isPrime = true; // Is the current number prime?
19
20 // Test if number is prime
21 for (int divisor = 2; divisor <= number / 2; divisor++)
22 {
23 if (number % divisor == 0)
24 {
25 // If true, the number is not prime
26 isPrime = false; // Set isPrime to false
27 break; // Exit the for loop
28 }
29 }
30
31 // Display the prime number and increase the count
32 if (isPrime)
33 {
34 count++; // Increase the count
35
36 if (count % NUMBER_OF_PRIMES_PER_LINE == 0)
37 // Display the number and advance to the new line
38 cout << setw(4) << number << endl;
39 else
40 cout << setw(4) << number;
41 }
42
43 // Check if the next number is prime
44 number++;
45 }
46
47 return 0;
48 }
This is a complex program for novice programmers. The key to developing a program- matic solution for this problem, and for many other problems, is to break it into subproblems and develop solutions for each of them in turn. Do not attempt to develop a complete solution in the first trial. Instead, begin by writing the code to determine whether a given number is prime, then expand the program to test whether other numbers are prime in a loop.
To determine whether a number is prime, check whether it is divisible by a number between 2 and number/2 inclusive. If so, it is not a prime number; otherwise, it is a prime number. For a prime number, display it. If the count is divisible by 10, advance to a new line. The program ends when the count reaches 50.
The program uses the break statement in line 27 to exit the for loop as soon as the number is found to be a nonprime. You can rewrite the loop (lines 21-29) without using the break statement, as follows:
for (int divisor = 2; divisor <= number / 2 && isPrime; divisor++)
{
// If true, the number is not prime
if (number % divisor == 0)
{
// Set isPrime to false, if the number is not prime
isPrime = false;
}
}
However, using the break statement makes the program simpler and easier to read in this case.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.