Check for prime number

Beginner Problems Basic Maths Easy

Prime number checking is a foundational concept in cryptography, particularly in public key encryption algorithms such as RSA
RSA relies intensively on the properties of prime numbers
The security of RSA is based on the fact that factoring large prime numbers is computationally intensive
Hence, when your browser secures a connection to a website (HTTPS), prime numbers are being used to encrypt the data

You are given an integer n. You need to 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:

Input: n = 5

Output: true

Explanation: The only divisors of 5 are 1 and 5 , So the number 5 is prime.

Input: n = 8

Output: false

Explanation: The divisors of 8 are 1, 2, 4, 8, thus it is not a prime number.

Input: n = 9

Constraints

1 <= n <= 5000

Company Tags

TCS Cognizant Accenture Infosys Capgemini Wipro IBM HCL Tech Mahindra MindTree

Editorial

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:

Initialize a counter with 0 to store the number of divisors.
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.
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.

Dry Run:

1 / 5

Solution:

#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;
}
class Solution {
    /* Function to find whether the
    number is prime or not */
    public boolean 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;
    }

    public static void main(String[] args) {
        int n = 5;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to find whether the
         given number is prime or not */
        boolean ans = sol.isPrime(n);
        
        if (ans) {
            System.out.println(n + " is a prime number.");
        } else {
            System.out.println(n + " is not a prime number.");
        }
    }
}
class Solution:
    # Function to find whether the
    # number is prime or not
    def isPrime(self, n):
        
        # Edge Case
        if n < 2:
            return False
            
        # Variable to store the 
        # count of divisors of n
        count = 0
        
        # Loop from 1 to n
        for i in range(1, n + 1):
            
            # Check if i is a divisor
            if n % i == 0:
                # Increment Count
                count += 1
        
        # If count is 2, n is prime
        if count == 2:
            return True
        # Else not prime
        return False

# Main function
if __name__ == "__main__":
    n = 5
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to find whether the
    # given number is prime or not
    ans = sol.isPrime(n)
    
    if ans:
        print(f"{n} is a prime number.")
    else:
        print(f"{n} is not a prime number.")
class Solution {
    /* Function to find whether the
    number is prime or not */
    isPrime(n) {
        // Edge Case
        if(n < 2) return false;
        
        /* Variable to store the 
        count of divisors of n */
        let count = 0;
        
        // Loop from 1 to n
        for (let 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;
    }
}

// Main function
const main = () => {
    let n = 5;
    
    /* Creating an instance of 
    Solution class */
    let sol = new Solution();
    
    /* Function call to find whether the
     given number is prime or not */
    let ans = sol.isPrime(n);
    
    if (ans) {
        console.log(n + " is a prime number.");
    } else {
        console.log(n + " is not a prime number.");
    }
}

main();

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.

Intuition:

The algorithm can be optimized by only iterating up to the square root of n when checking for divisors. This is because if n has a divisor i, then another divisor (counterpart divisor) for n is (n/i).

Approach:

Initialize a counter with 0 to store the number of divisors.
Start iterating from 1 to the square root of 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. Also, if the counterpart divisor is not the same as the divisor, increment the counter by 1.
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.

Dry Run:

1 / 4

Solution:

#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 square root of n
        for(int i = 1; i <= sqrt(n); ++i) {
            
            // Check if i is a divisor
            if(n % i == 0) {
                // Increment Count
                count = count + 1;
                
                /* Check if counterpart divisor
                is different from original divisor */
                if(n / i != i) {
                    
                    // 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;
}
class Solution {
    /* Function to find whether the
    number is prime or not */
    public boolean 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 square root of n
        for(int i = 1; i <= Math.sqrt(n); ++i) {
            
            // Check if i is a divisor
            if(n % i == 0) {
                // Increment Count
                count = count + 1;
                
                /* Check if counterpart divisor
                is different from original divisor */
                if(n / i != i) {
                    
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        if(count == 2) return true;
        // Else not prime
        return false;
    }

    public static void main(String[] args) {
        int n = 5;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to find whether the
         given number is prime or not */
        boolean ans = sol.isPrime(n);
        
        if (ans) {
            System.out.println(n + " is a prime number.");
        } else {
            System.out.println(n + " is not a prime number.");
        }
    }
}
import math 

class Solution:
    # Function to find whether the
    # number is prime or not
    def isPrime(self, n):
        
        # Edge Case
        if n < 2:
            return False
            
        # Variable to store the 
        # count of divisors of n
        count = 0
        
        # Loop from 1 to square root of n
        for i in range(1, int(math.sqrt(n)) + 1):
            
            # Check if i is a divisor
            if n % i == 0:
                # Increment Count
                count += 1
                
                # Check if counterpart divisor
                # is different from original divisor
                if n // i != i:
                    
                    # Increment count
                    count += 1
        
        # If count is 2, n is prime
        return count == 2

# Main function
if __name__ == "__main__":
    n = 5
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to find whether the
    # given number is prime or not
    ans = sol.isPrime(n)
    
    if ans:
        print(f"{n} is a prime number.")
    else:
        print(f"{n} is not a prime number.")
class Solution {
    /* Function to find whether the
    number is prime or not */
    isPrime(n) {
        // Edge Case
        if(n < 2) return false;
        
        /* Variable to store the 
        count of divisors of n */
        let count = 0;
        
        // Loop from 1 to square root of n
        for (let i = 1; i <= Math.sqrt(n); ++i) {
            
            // Check if i is a divisor
            if (n % i === 0) {
                // Increment Count
                count = count + 1;
                
                /* Check if counterpart divisor
                is different from original divisor */
                if (n / i !== i) {
                    
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        return count === 2;
    }
}

// Main function
const main = () => {
    let n = 5;
    
    /* Creating an instance of 
    Solution class */
    let sol = new Solution();
    
    /* Function call to find whether the
     given number is prime or not */
    let ans = sol.isPrime(n);
    
    if (ans) {
        console.log(n + " is a prime number.");
    } else {
        console.log(n + " is not a prime number.");
    }
}

main();

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.

Code

Problem List

Check for prime number

Examples:

Constraints

Company Tags

Editorial

Intuition:

Approach:

Edge Case:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Edge Case:

Dry Run:

Solution:

Complexity Analysis:

Notes

Code