C++ Program To Check Prime Number By User Defined Function

Prime numbers are fundamental in mathematics and computer science, playing a crucial role in cryptography, number theory, and algorithm design. Being able to efficiently determine if a number is prime is a valuable skill. In this article, you will learn how to write a C++ program that uses a user-defined function to check if a given number is prime.

Problem Statement

The core problem is to develop a reliable and reasonably efficient method to classify an integer as either a prime number or a composite number. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Numbers like 2, 3, 5, 7, 11 are primes, while 4, 6, 9, 10 are not.

Example

Consider checking if the number 13 is prime:

• Input: 13
• Output: 13 is a prime number.

Consider checking if the number 10 is prime:

• Input: 10
• Output: 10 is not a prime number.

Background & Knowledge Prerequisites

To understand and implement this C++ program, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types (e.g., int), and input/output operations (cin, cout).
• Functions: How to declare, define, and call user-defined functions, including parameters and return types.
• Conditional Statements: Using if, else if, and else for decision-making.
• Loops: Employing for or while loops for iteration.
• Boolean Data Type: Understanding bool and its values (true, false).

Use Cases or Case Studies

Checking for prime numbers is not just an academic exercise; it has several practical applications:

• Cryptography: Prime numbers are the backbone of public-key cryptography algorithms like RSA, where large prime numbers are used to generate keys.
• Hashing: Some hashing algorithms use prime numbers to reduce collisions and distribute data evenly across hash tables.
• Random Number Generation: Prime numbers can be incorporated into algorithms for generating pseudo-random numbers.
• Number Theory Research: They are essential for research in number theory, including factorization, primality testing of very large numbers, and the distribution of primes.
• Educational Tools: Demonstrating primality testing helps students grasp concepts of divisibility, functions, and algorithmic efficiency.

Solution Approaches

We will focus on a common and efficient approach involving a user-defined function that tests for divisibility up to the square root of the given number.

Using a User-defined Function to Check Primality

This approach defines a boolean function isPrime() that takes an integer as input. It first handles edge cases (numbers less than or equal to 1, and 2), then checks for divisibility by 2, and finally iterates through odd numbers up to the square root of the input to find any divisors.

// Check Prime Number by User-defined Function
#include <iostream>
#include <cmath> // Required for sqrt() function

// Function to check if a number is prime
bool isPrime(int num) {
    // Step 1: Handle edge cases
    if (num <= 1) {
        return false; // Numbers less than or equal to 1 are not prime
    }
    if (num == 2) {
        return true;  // 2 is the only even prime number
    }
    if (num % 2 == 0) {
        return false; // All other even numbers are not prime
    }

    // Step 2: Check for divisibility from 3 up to sqrt(num)
    // We only need to check odd divisors
    for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) {
            return false; // Found a divisor, so it's not prime
        }
    }

    // Step 3: If no divisors were found, the number is prime
    return true;
}

int main() {
    // Step 1: Declare a variable to store user input
    int number;

    // Step 2: Prompt the user to enter a number
    std::cout << "Enter a positive integer: ";
    std::cin >> number;

    // Step 3: Call the isPrime function and display the result
    if (isPrime(number)) {
        std::cout << number << " is a prime number." << std::endl;
    } else {
        std::cout << number << " is not a prime number." << std::endl;
    }

    return 0;
}

Run

Sample Output

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

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

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

Stepwise Explanation

1. #include and #include : These lines include the necessary libraries for input/output operations and mathematical functions like sqrt(), respectively.
2. isPrime(int num) Function Definition:
   • It takes an integer num as input and returns a bool value (true if prime, false otherwise).

1. main() Function:
   • Declares an integer number to store user input.

Conclusion

Using a user-defined function to check for prime numbers significantly improves code organization, reusability, and readability. By incorporating optimizations such as handling edge cases, checking only odd divisors, and iterating only up to the square root of the number, the program efficiently determines primality for a given integer. This fundamental algorithm is a cornerstone for many advanced computational tasks involving number theory.

Summary

• A prime number is a natural number greater than 1 with no positive divisors other than 1 and itself.
• A user-defined function (isPrime) enhances code modularity and allows for easy reuse of the primality test logic.
• Optimization techniques include:
• Handling num <= 1 as not prime.
• Treating 2 as prime and all other even numbers as non-prime.
• Checking for divisors only up to sqrt(num).
• Incrementing the divisor check by 2 (checking only odd numbers).
• The cmath library and sqrt() function are essential for efficient square root calculation.
• The program prompts the user for input and clearly states whether the entered number is prime or not.