Trap 6 - Prime Number

◀ Trap 5 - The cin Operator▶ Trap 7 - Factorial Amazon Writing a function can be tricky. When the function involves many mathematical calculations and formulas you need to be extra careful. The following program tests to see if an integer inputted by the user is a prime number. However, there are several bugs in it. Locate the bugs and correct them.

#include <iostream>
using namespace std;

bool isPrime(int n){
	if(n%2==0) return false;
	int m=3;
	while(m*m<n){
		if(n%m==0) return false;
		m += 2;
	}
	return true;
}
int main(){
	int input;
	cout<<"Please enter an integer: ";
	cin>>input;
	if(isPrime(input))
		cout<<input<<" is a prime number.\n";
	else
		cout<<input<<" is not a prime number.\n";
	return 0;
}

Solution
First of all, we need to know exactly what a prime number is. By definition, a prime number is an integer which is not evenly divisible by any integer except 1 and itself, with the exception that 1 is not a prime number. Therefore, the first several prime numbers are 2, 3, 5, 7, 11, 13.

This concept should make it obvious that the first bug in this program is that it thinks 1 is a prime number. Also, isPrime() thinks that none of the even numbers is a prime number, but 2 is one.

Finally, we would like to know what the program thinks about perfect squares such as 9, 14, and 25. The while loop in isPrime() tests whether m*m<n because if n has any divisors other than 1 and itself, at least one of them must be less than square root of n.

For example, 9 is a prime; however, the while loop fails when m equals 3 (thus returns true). This should not happen, so we should change < to <=.

Here is the corrected program:

#include <iostream>
using namespace std;

bool isPrime(int n){
	if(n==2) return true;
	if(n%2==0 || n==1) return false;
	int m=3;
	while(m*m<=n){
		if(n%m==0) return false;
		m += 2;
	}
	return true;
}
int main(){
	int input;
	cout<<"Please enter an integer: ";
	cin>>input;
	if(isPrime(input))
		cout<<input<<" is a prime number.\n";
	else
		cout<<input<<" is not a prime number.\n";
	return 0;
}

By examining this exercise, you should have learned that a correctly working function is crucial for the correctness of a program. In this example there is only one function.

What if you want to do more to the prime number the user enters? You write more functions to process the number, and you end up getting incorrect results but are at a loss to figure out where they originate. Therefore, testing a function individually helps programmers locate a bug, if any.

Also, correct logic is crucial to writing a good function. In this case, if we knew exactly what numbers are prime, we probably would not have made any mistakes.

Next let’s look at a buggy program to find its bugs!
◀ Trap 5 - The cin Operator▶ Trap 7 - Factorial