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

int main() {
    int num;
    bool isPrime = true;
    
    cout << "Enter a number: ";
    cin >> num;
    
    if (num <= 1) {
        isPrime = false;
    } else {
        for (int i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                isPrime = false;
                break;
            }
        }
    }
    
    if (isPrime) {
        cout << num << " is a prime number" << endl;
    } else {
        cout << num << " is not a prime number" << endl;
    }
    
    return 0;
}

Enter a number: 17
17 is a prime number

Prime Check in C++

This program checks whether a given number is prime. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This program demonstrates efficient prime checking using the square root optimization, which is a fundamental algorithm in number theory and computer science.

What is a Prime Number?

A prime number is a natural number greater than 1 that:

• Is divisible only by 1 and itself
• Has exactly two distinct positive divisors

Examples of prime numbers:

• 2 (smallest prime, only even prime)

• 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Examples of non-prime (composite) numbers:

• 4 (divisible by 1, 2, 4)

• 6 (divisible by 1, 2, 3, 6)

• 8 (divisible by 1, 2, 4, 8)

• 9 (divisible by 1, 3, 9)

• 1 (not prime, only one divisor)

Special cases:

• 1 is NOT prime (only one divisor)

• 2 is the only even prime number

• All other even numbers (>2) are composite

The Square Root Optimization

Key insight: If a number n is composite, it must have a divisor less than or equal to √n.

Why this works:

• If n = a × b, at least one of a or b must be ≤ √n
• If both were > √n, then a × b > n (contradiction)
• So we only need to check divisors up to √n

Example:

• To check if 17 is prime:
  • √17 ≈ 4.12
  • Check divisors: 2, 3, 4
  • None divide 17 → ## Prime ✅

Algorithm

1. Check if number ≤ 1 → not prime
2. Check if number == 2 → prime
3. Check if number is even → not prime (except 2)
4. Check divisors from 3 to √n (odd numbers only)
5. If any divisor found → not prime
6. If no divisors found → prime

Summary

• Prime number has exactly two divisors: 1 and itself
• Square root optimization: only check divisors up to √n
• This reduces time complexity from O(n) to O(√n)
• Check special cases: 1, 2, even numbers
• This algorithm is fundamental in number theory and cryptography

This program teaches:

• Efficient prime checking algorithm
• Square root optimization
• Boolean flags for tracking state
• Input validation
• Mathematical optimization techniques

Understanding prime checking helps in:

• Cryptography (RSA encryption)
• Hash functions
• Random number generation
• Mathematical research
• Computer security