Prime Number in C++

 

A prime number is a number that is greater than 1 and has no divisors other than 1 and itself. In other words, a prime number has exactly two distinct positive divisors: 1 and the number itself.

For example:

• 2 is a prime number (divisors are 1 and 2).
• 5 is a prime number (divisors are 1 and 5).
• 9 is not a prime number (divisors are 1, 3, and 9).

Below is an example of a C++ program that checks if a number is prime.

---

1️⃣ Example: Check if a Number is Prime

Here’s a C++ program that checks whether a number is prime or not:

#include <iostream>
using namespace std;

bool isPrime(int num) {
    // 1 is not a prime number
    if (num <= 1) {
        return false;
    }

    // Check for divisors from 2 to sqrt(num)
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;  // num is divisible by i, so it's not prime
        }
    }

    return true;  // num is prime
}

int main() {
    int N;

    // Taking input from the user
    cout << "Enter a positive integer: ";
    cin >> N;

    if (isPrime(N)) {
        cout << N << " is a prime number." << endl;
    } else {
        cout << N << " is not a prime number." << endl;
    }

    return 0;
}

Explanation:

1. Input: The user is asked to input a number N.
2. Prime Check: The function isPrime() checks if the number is prime by checking if any number from 2 to sqrt(N) divides the number evenly. If a divisor is found, the function returns false. Otherwise, it returns true, indicating the number is prime.
3. Output: The program prints whether the input number is prime or not.

Output (Example when N = 11):

Enter a positive integer: 11
11 is a prime number.

Output (Example when N = 15):

Enter a positive integer: 15
15 is not a prime number.

---

2️⃣ Example: Prime Numbers Between 1 and N

If you want to find all prime numbers between 1 and a given number N, you can modify the program as follows:

#include <iostream>
using namespace std;

bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int N;

    // Taking input from the user
    cout << "Enter a positive integer: ";
    cin >> N;

    cout << "Prime numbers between 1 and " << N << " are: ";

    // Loop through all numbers from 1 to N
    for (int i = 2; i <= N; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }

    cout << endl;
    return 0;
}

Explanation:

• The function isPrime() is the same as before.
• The main() function loops through all numbers from 2 to N and prints those that are prime.

Output (Example when N = 20):

Enter a positive integer: 20
Prime numbers between 1 and 20 are: 2 3 5 7 11 13 17 19

---

3️⃣ Optimizing Prime Number Check

The above approach is efficient enough for small numbers, but if you're dealing with larger numbers, there are optimizations that can improve the performance.

Optimizations:

1. Check for even numbers: If a number is greater than 2 and is even, it's not prime.
2. Check divisibility only up to sqrt(N): We don't need to check divisibility beyond the square root of N, because factors of N would have already appeared in pairs below sqrt(N).

Here's an optimized version of the prime check:

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

bool isPrime(int num) {
    if (num <= 1) return false;    // 1 is not prime
    if (num == 2) return true;     // 2 is prime
    if (num % 2 == 0) return false; // Even numbers greater than 2 are not prime

    // Check divisibility from 3 to sqrt(num) with step 2 (only odd numbers)
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;  // num is divisible by i, so it's not prime
        }
    }

    return true;  // num is prime
}

int main() {
    int N;

    // Taking input from the user
    cout << "Enter a positive integer: ";
    cin >> N;

    if (isPrime(N)) {
        cout << N << " is a prime number." << endl;
    } else {
        cout << N << " is not a prime number." << endl;
    }

    return 0;
}

Explanation:

• The optimized isPrime() function checks if num is less than or equal to 1, if it's 2, or if it’s an even number greater than 2.
• For numbers greater than 2, it checks divisibility from 3 to sqrt(num) while skipping even numbers (incrementing i by 2).

Output (Example when N = 29):

Enter a positive integer: 29
29 is a prime number.

---

4️⃣ Key Points to Remember:

• A prime number has no divisors other than 1 and itself.
• We can optimize the prime number check by only iterating up to the square root of the number.
• Even numbers greater than 2 are never prime (except for 2 itself).
• For large ranges or very large numbers, further optimization techniques or prime number algorithms like the Sieve of Eratosthenes might be needed.

Would you like to explore the Sieve of Eratosthenes or any other related topics such as perfect numbers or Fibonacci numbers?