Determining whether a number is a prime number or a composite number is an interesting (and sometime complex) subject in mathematics. For new programmers, especially who have started to learn C++, it can be a good practice to write code which can determine whether a number is prime number or a composite number.
What is a prime number?
In most simplest terms, if a number is only divisible by 1 and that number then that it is a prime number. In other words, for any given number, if that number is a product of only two factors; one of them is 1 and other one is that number itself, then it is a prime number.
You can read more in detail in the Wikipedia’s article.
How to determine whether a number is a prime number or a composite number?
Let’s first think in most simplest manner, using brute force (also known as trial division in Mathematics). Considering, that we are given a number X. We can divide X with all number from 2 to X-1. If modulus (remainder) of all these division is not a zero then it’s a prime number. In C++, to get modulus of any division, we use modulo operator which is “%”. Consider following example of using division operator and modulo operator in C++:
int division = 6 / 2; // Gives 3 as result int modulus = 6 % 2; // Gives 0 as result
Using this knowledge, let’s find out if 43 is a prime or a composite number using C++ code:
#include <iostream>
int main()
{
int number = 43;
bool notPrime = false;
for (auto i = 2; i < number; i++)
{
if ((number % i) == 0)
{
notPrime = true;
break;
}
}
if (notPrime)
std::cout << number << " is a composite number\n";
else
std::cout << number << " is a prime number\n";
return 0;
}
Finding all prime numbers between 2 and 100
With nested For-Loops we can find out all prime numbers between 2 and 100. It’s rather simpler than you might think:
#include <iostream>
int main()
{
bool numberIsPrime = true;
for (auto number = 2; number <= 100; number++)
{
numberIsPrime = true;
for (auto i = 2; i < number; i++)
{
if ((number % i) == 0)
{
numberIsPrime = false;
break;
}
}
if (numberIsPrime)
std::cout << number << " is a prime number\n";
}
return 0;
}
Find all prime numbers up to user’s input
Although above code works but it’s static. What if user wants to find out all prime number between 2 and let’s say 1000. For that we can ask user to give us a number and C++ code will try to find all prime between 2 and that given number and display it on screen.
#include <iostream>
int main()
{
int userInput = 0;
bool numberIsPrime = true;
std::cout << "Enter number: ";
std::cin >> userInput;
for (auto number = 2; number <= userInput; number++)
{
numberIsPrime = true;
for (auto i = 2; i < number; i++)
{
if ((number % i) == 0)
{
numberIsPrime = false;
break;
}
}
if (numberIsPrime)
std::cout << number << " is a prime number\n";
}
return 0;
}
Validation of user input
If you run above code then it works perfectly as long as user give us a correct number. However, what if user give us invalid number, perhaps a string? We’ll get unhandled error exception at std::cin >> userInput;. Therefore, we need to validate user input before we can proceed.
#include <iostream>
#include <string>
int main()
{
std::string userInput;
bool numberIsPrime = true;
int userNumber = 0;
std::cout << "Enter number: ";
std::getline(std::cin, userInput);
try
{
userNumber = std::stoi(userInput);
}
catch (const std::exception&)
{
std::cerr << "Invalid number was given.\n";
return 1; // Exit with an error number
}
for (auto number = 2; number <= userNumber; number++)
{
numberIsPrime = true;
for (auto i = 2; i < number; i++)
{
if ((number % i) == 0)
{
numberIsPrime = false;
break;
}
}
if (numberIsPrime)
std::cout << number << " is a prime number\n";
}
return 0;
}
Complete code with more validations on user input
We can write few more validations on user input to make sure it is a correct number for our calculation. Moreover, we can compact output by using a tab character to separate numbers instead of newline. Our complete code would be like following:
#include <iostream>
#include <string>
int main()
{
std::string userInput;
bool numberIsPrime = true;
int userNumber = 0;
// Get user input
std::cout << "Enter number: ";
std::getline(std::cin, userInput);
// Validate user input
if (userInput.empty())
{
std::cerr << "No input was given.\n";
return 1; // Exit with an error number
}
// Validate by converting user input to integer
try
{
userNumber = std::stoi(userInput);
}
catch (const std::exception&)
{
std::cerr << "Invalid number was given.\n";
return 1;
}
// Further validate user input
if (userNumber < 0)
{
std::cerr << "Please enter a positive number.\n";
return 1;
}
if (userNumber < 2)
{
std::cerr << "Please enter a number larger than 1.\n";
return 1;
}
// Find all prime numbers between 2 and number given by user
for (auto number = 2; number <= userNumber; number++)
{
numberIsPrime = true;
for (auto i = 2; i < number; i++)
{
if ((number % i) == 0)
{
numberIsPrime = false;
break;
}
}
if (numberIsPrime)
std::cout << number << "\t";
}
// Flush the output stream and also output newline character.
std::cout << std::endl;
return 0;
}
You can also find above code in Github’s Gist here.
You may also be interested in following articles: