C++ Program to Check Prime Number

C++ Program to Check Prime Number

By /

Prime numbers are numbers greater than 1 that have no divisors other than 1 and themselves. They play a key role in mathematics, cryptography, and computer algorithms. Learning how to check for prime numbers in C++ is a great exercise for beginners because it teaches the basics of loops, conditionals, functions, and simple optimization techniques. In this article, we will explore multiple methods to check prime numbers, starting from the simplest approach and progressing to more efficient and advanced methods.

Program 1: Basic Method to Check Prime Number

This is the most straightforward method to determine whether a number is prime. The program loops through all numbers from 2 up to one less than the given number and checks if any number divides the input evenly. While this method is not efficient for large numbers, it provides a clear understanding of the concept of prime numbers and how loops and conditionals work in C++.

#include <iostream>

using namespace std;

int main() {

    int n;
    bool isPrime {true};

    cout << "Enter a number: " << endl;
    cin >> n;

    if(n <= 1) {

        isPrime = false;

    } else {

        for(int i = 2; i < n; i++) {

            if(n % i == 0) {
                isPrime = false;
                break;
            }

        }

    }

    if(isPrime)
        cout << n << " is a prime number." << endl;

    else
        cout << n << " is not a prime number." << endl;

    return 0;

}

In this program, we begin by assuming that the number is prime. The loop then checks each number from 2 up to n-1, and if any of them divide the input evenly, the number is marked as not prime. Beginners can benefit from this approach by seeing exactly how conditional statements and loops interact to solve a mathematical problem.

Program 2: Optimized Method Using Square Root

We can make prime checking more efficient by recognizing that factors of a number larger than its square root will always have corresponding factors smaller than the square root. This means we only need to check divisibility up to the square root of the number. By caching the square root in a variable, we avoid repeated calculations in each loop iteration, which improves performance for larger inputs.

#include <iostream>
#include <cmath>

using namespace std;

int main() {

    int n;
    bool isPrime {true};

    cout << "Enter a number: " << endl;
    cin >> n;

    if(n <= 1) {

        isPrime = false;

    } else {

        double sqrtN = sqrt(n); // Cache the square root for efficiency

        for(int i = 2; i <= sqrtN; i++) {

            if(n % i == 0) {
                isPrime = false;
                break;
            }

        }

    }

    if(isPrime)
        cout << n << " is a prime number." << endl;

    else
        cout << n << " is not a prime number." << endl;

    return 0;

}

This program demonstrates how simple mathematical reasoning can optimize a program. By understanding that we only need to check divisibility up to the square root, beginners can learn how to reduce computational work without changing the logic of the algorithm.

Program 3: Using a Custom Function

Encapsulating the prime check in a function allows us to reuse the logic for multiple numbers and write cleaner, modular code. This approach shows beginners how functions improve readability and maintainability, and how the same logic can be applied repeatedly without duplicating code.

#include <iostream>
#include <cmath>

using namespace std;

bool isPrimeNumber(int n) {

    if(n <= 1) return false;

    double sqrtN = sqrt(n);

    for(int i = 2; i <= sqrtN; i++) {
        if(n % i == 0) return false;
    }

    return true;

}

int main() {

    int n;

    cout << "Enter a number: " << endl;
    cin >> n;

    if(isPrimeNumber(n))
        cout << n << " is a prime number." << endl;

    else
        cout << n << " is not a prime number." << endl;

    return 0;

}

In this example, the function isPrimeNumber() handles the prime checking while the main program focuses on user input and output. Beginners can clearly see the advantage of breaking programs into smaller, reusable pieces while maintaining the same efficiency as the square root method.

Program 4: 6k ± 1 Optimization

For numbers greater than 3, all prime numbers are of the form 6k ± 1. This observation helps us skip multiples of 2 and 3, significantly reducing the number of checks when verifying primality. This method is especially useful for numbers that are moderately large but still manageable with deterministic checks.

What is 6k ± 1?

The 6k ± 1 method is a simple mathematical shortcut for identifying potential prime numbers above 3. Any integer can be expressed as 6k, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5. Among these, numbers divisible by 2 or 3 (6k, 6k+2, 6k+3, 6k+4) are never prime. That leaves only numbers of the form 6k − 1 or 6k + 1 as candidates for primes. By focusing only on these numbers, we reduce unnecessary computations while still correctly identifying primes.

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime6k(int n) {

    if(n <= 1) return false;
    if(n <= 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;

    int limit = sqrt(n);

    for(int i = 5; i <= limit; i += 6) {

        if(n % i == 0 || n % (i + 2) == 0)
            return false;

    }

    return true;

}

int main() {

    int n;
    cout << "Enter a number: " << endl;
    cin >> n;

    if(isPrime6k(n))
        cout << n << " is a prime number." << endl;

    else
        cout << n << " is not a prime number." << endl;

    return 0;

}

In this program, the loop starts from 5 and checks numbers of the form 6k − 1 and 6k + 1 up to the square root of n. By skipping obvious non-prime candidates, we reduce the number of iterations while ensuring accuracy. Beginners can see how simple mathematical patterns like 6k ± 1 can make their programs more efficient without complicating the logic.

Program 5: Miller-Rabin Primality Test (Probabilistic)

For very large numbers, deterministic methods may be slow. The Miller-Rabin test is a probabilistic algorithm that can quickly determine whether a number is likely prime. Although it does not provide absolute certainty for all numbers, it is widely used in cryptography and scenarios where speed is crucial.

#include <iostream>
#include <cstdlib>

using namespace std;

long long modPow(long long base, long long exp, long long mod) {

    long long result = 1;
    base %= mod;

    while(exp > 0) {

        if(exp % 2 == 1) result = (result * base) % mod;

        base = (base * base) % mod;
        exp /= 2;

    }

    return result;

}

bool millerTest(long long d, long long n) {

    long long a = 2 + rand() % (n - 4);
    long long x = modPow(a, d, n);

    if(x == 1 || x == n-1) return true;

    while(d != n-1) {

        x = (x * x) % n;
        d *= 2;
        if(x == 1) return false;
        if(x == n-1) return true;

    }

    return false;

}

bool isPrimeMR(long long n, int k=5) {

    if(n <= 1 || n == 4) return false;
    if(n <= 3) return true;

    long long d = n-1;

    while(d % 2 == 0) d /= 2;

    for(int i = 0; i < k; i++)
        if(!millerTest(d, n))
            return false;

    return true;

}

int main() {

    long long n;

    cout << "Enter a number: " << endl;
    cin >> n;

    if(isPrimeMR(n))
        cout << n << " is probably a prime number." << endl;

    else
        cout << n << " is not a prime number." << endl;

    return 0;

}

This program illustrates a probabilistic approach that balances speed and reliability. By running the test multiple times, we can reduce the chance of false positives. Beginners interested in cryptography and large-number computation will find this method very practical.

Frequently Asked Questions (FAQ)

Here are some common questions beginners ask about prime numbers in C++:

Q1: What is the smallest prime number?
The smallest prime number is 2. It is also the only even prime number.

Q2: Can 1 be a prime number?
No, 1 is not considered prime because it has only one divisor.

Q3: Why use the square root method?
Checking up to the square root reduces the number of iterations, making the program faster for larger numbers.

Q4: Can I use a function to check multiple numbers?
Yes, creating a prime-checking function allows you to reuse the logic for multiple numbers efficiently.

Q5: Which method is best for large numbers?
Probabilistic methods like Miller-Rabin are preferred for very large numbers, especially in cryptography, because they are faster than deterministic methods.

Conclusion

Checking prime numbers in C++ teaches important programming concepts like loops, conditionals, modular functions, and optimization techniques. We explored five methods: the basic loop method, the square root method, a reusable function, 6k ± 1 optimization, and the Miller-Rabin probabilistic test. Beginners should start with simple loops to understand the logic, then use optimized or modular methods for more efficient and reusable code. Advanced users can apply probabilistic tests for very large numbers. Practicing these methods strengthens both programming skills and mathematical reasoning.

Additional & References

Understanding prime numbers is fundamental for algorithms, cryptography, and mathematical computations. Beginners are encouraged to practice checking multiple numbers, generating prime sequences, and exploring optimizations.

References:

Related Posts

Scroll to Top