🔍 Check Prime Number Using Optimized Trial Division in C++

🔍 Check Prime Number Using Optimized Trial Division in C++

A prime number is a natural number greater than 1 that is not divisible by any number other than 1 and itself. Prime numbers play a vital role in number theory, cryptography, and programming interviews.

💡 What Is Optimized Trial Division?

In a naive approach, we check divisibility from 2 to n-1. However, this is inefficient. An optimized trial division method improves performance by:

• Eliminating even numbers after checking 2
• Checking up to √n instead of n

📄 C++ Code: Optimized Prime Check

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;

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

int main() {
    int number;
    cout << "Enter a number: ";
    cin >> number;

    if (isPrime(number))
        cout << number << " is a prime number.";
    else
        cout << number << " is not a prime number.";

    return 0;
}
    

✅ Sample Output

Enter a number: 29  
29 is a prime number.
  

📝 How It Works

• Any number ≤ 1 is not prime.
• 2 is the only even prime number.
• We skip all even numbers after 2 for efficiency.
• We only check divisors up to the square root of n.

📘 Definition: Prime Number Check with Optimized Trial Division

Checking for prime using optimized trial division involves verifying if a number is divisible by any number up to its square root. The process skips even numbers (except 2), improving performance, especially for large inputs.

🎯 Conclusion

This method is ideal for quickly determining if a number is prime and is widely used in competitive programming, cryptography, and algorithms that rely on number theory. The optimized logic ensures faster performance with minimal code complexity.