Problem Statement

You are given an integer n. Check if the number is prime or not, return true if it is a prime number, otherwise return false.

A Prime number is a number which has no divisors except 1 and itself.

Examples

Example 1:

Input: n = 7
Output: true

Explanation: 7's divisors are 1 and 7 itself. so it is a prime number.

Example 2:

Input: n = 10
Output: false

Explanation: 10's divisors are 1, 2, 5 and 10 itself. As it has divisors other than 1 and number itself. So it is not a prime number.

Approaches

1️⃣ Brute Force Approach

Intuition:

Given a number, all its divisors can be counted. Since a prime number has only two divisors, which are 1 and the number itself, the count of divisors for a prime number will always be 2. If the given number has two divisors, then it is prime, else it is not.

Approach:

1. Initialize a counter with 0 to store the number of divisors.
2. Start iterating from 1 to the number using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable. If it is divisible completely, increment the counter by 1.
3. After the iterations are over, the counter stores the number of divisors the given number had. If the counter is equal to 2, the number is prime, else it is not.

Edge Case:

The prime numbers start from 2. Thus, if a number is less than 2, it can be directly said as non-prime.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find whether the
    number is prime or not */
    bool isPrime(int n) {
        // Edge case
        if(n < 2) return false;
        
        /* Variable to store the 
        count of divisors of n */
        int count = 0;
        
        // Loop from 1 to n
        for (int i = 1; i <= n; ++i) {
            
            // Check if i is a divisor
            if (n % i == 0) {
                // Increment Count
                count = count + 1;
            }
        }
        
        // If count is 2, n is prime
        if (count == 2) return true;
        // Else not prime
        return false;
    }
};

int main() {
    int n = 5;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
     given number is prime or not */
    bool ans = sol.isPrime(n);
    
    if (ans) {
        cout << n << " is a prime number." << endl;
    } else {
        cout << n << " is not a prime number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) – Looping N times to find the count of all divisors of N.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.

2️⃣ Square Root (Optimal) Approach

Intuition:

A better approach would be to iterate only up to the square root of n. If n has any divisors larger than its square root, there must be a corresponding divisor smaller than the square root.

• If n is divisible by any number between 2 and sqrt(n), then it is not a prime number.

Approach:

1. Check divisibility from 2 to sqrt(n).
2. If divisible by any number in this range, n is not prime.

Edge Case:

The prime numbers start from 2. Thus, if a number is less than 2, it can be directly said as non-prime.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find whether the
    number is prime or not */
    bool isPrime(int n) {
        // Edge case
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i <= sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;    
   }
};

int main() {
    int n = 5;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
     given number is prime or not */
    bool ans = sol.isPrime(n);
    
    if (ans) {
        cout << n << " is a prime number." << endl;
    } else {
        cout << n << " is not a prime number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(sqrt(N)) – Looping sqrt(N) times to find the count of all divisors of N.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.