How to Check if a Number Is Prime in C++
- Use Trial Division Method to Check if a Number Is Prime in C++
- Use Relatively Optimized Method to Check if a Number Is Prime
This article will explain several methods of how to check if a number is prime in C++.
Use Trial Division Method to Check if a Number Is Prime in C++
The primality test is the algorithm’s name that determines whether the given number is a prime number. The simple solution to check if a number is prime would be to iterate over the natural numbers from the one to the given number and check if the division has no remainder.
Several insights can improve this method. The first - all divisors of integer n are less than or equal to n/2, which means that the search space has been reduced. In the following example, we also implement a validateInput function to take the integer from the user and verify that it is stored successfully in a corresponding variable. The program runs in an infinite loop to continuously ask the user for the number and then print the message to the cout stream.
#include <algorithm>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;
bool isPrime(unsigned long long &n) {
if (n <= 1) return false;
for (uint i = 2; i < n; ++i)
if (n % i == 0) return false;
return true;
}
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter the natural number: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter a valid natural number!\n";
cin.clear();
cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
int main() {
unsigned long long num;
while (true) {
validateInput(num);
isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
}
exit(EXIT_SUCCESS);
}
Use Relatively Optimized Method to Check if a Number Is Prime
We can continue optimizing the previous method by testing only the divisors less than or equal to square root from the n, which happens to be true for all natural numbers. Note that all primes greater than 3 can be represented as a form of 6k+-1, where k is an integer greater than zero. It further implies that the efficient method happens to be testing the number divisibility for the values of 2 and 3. If the previous condition does not eliminate the given number as not-prime, then all numbers of form 6k+-1 should be tested that is also less than the square root of n. Note that, validateInput breaks from the while loop when terminal interrupt is caught (e.g. Ctrl+D).
#include <algorithm>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter the natural number: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter a valid natural number!\n";
cin.clear();
cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
bool isPrime(unsigned long long &n) {
if (n <= 3) return n > 1;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0) return false;
return true;
}
int main() {
unsigned long long num;
while (true) {
validateInput(num);
isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
}
exit(EXIT_SUCCESS);
}
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook