Check for prime number
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:
Solution:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
#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;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445
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.");
}
}
}12345678910111213141516171819202122232425262728293031323334353637383940414243
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.")123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
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:
Solution:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
#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;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
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.");
}
}
}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
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.")123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
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.
Notes
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.
Code
Test Cases
3 case(s)
Input
Expected Output
true
Your Output
Not executed yet
Status:
Waiting
Runtime:
-
Input
Expected Output
false
Your Output
Not executed yet
Status:
Waiting
Runtime:
-
Input
Expected Output
true
Your Output
Not executed yet
Status:
Waiting
Runtime:
-
Facts
- • 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