Check if a Number Is Prime in C++

  1. Use Trial Division Method to Check if a Number Is Prime in C++
  2. 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 <iostream>
#include <string>
#include <algorithm>

using std::cout; using std::cin;
using std::endl; using std::string;
using std::numeric_limits;

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 <iostream>
#include <iostream>
#include <string>
#include <algorithm>

using std::cout; using std::cin;
using std::endl; using std::string;
using std::numeric_limits;

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);
}
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - C++ Int

  • Parse Int From String in C++
  • Convert String to Int in C++