Problem Statement: Given a number, check whether it is prime or not. A prime number is a natural number that is only divisible by 1 and by itself.
Examples 1 2 3 5 7 11 13 17 19 …
Examples
Example 1: Input: N = 3 Output: Prime Explanation: 3 is a prime number Example 2: Input: N = 26 Output: Non-Prime Explanation: 26 is not prime
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Approach
Algorithm / Intuition
Solution 1: Using Iterative solution
Approach:
A prime number is a natural number that is only divisible by 1 and by itself. Examples 1 2 3 5 7 11 13 17 19 …
Running a for loop for checking if the number is divisible by a number from 2 to a number less than a given number.
And then checking if the number is divisible by the numbers from 2 to the number less than a given number
Then, If the remainder is zero, that means it is divisible and hence not a prime number.
If the loop runs till square root and none of the numbers divided it completely. So it is the Prime number.
Code
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int N) {
for (int i = 2; i < N; i++) {
if (N % i == 0) {
return false;
}
}
return true;
}
int main() {
int n = 11;
bool ans = isPrime(n);
if (n != 1 && ans == true) {
cout << "Prime Number";
} else {
cout << "Non Prime Number";
}
return 0;
}
Output: Prime Number
class Solution {
public static boolean isPrime(int N) {
for (int i = 2; i < N; i++) {
if (N % i == 0) {
return false;
}
}
return true;
}
public static void main(String args[]) {
int n = 20;
boolean ans = (isPrime(n));
if (n != 1 && ans == true) {
System.out.println("Prime Number");
} else {
System.out.println("Non-Prime Number");
}
}
}
Output: Prime Number
def isPrime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
if __name__ == "__main__":
n = 11
ans = isPrime(n)
if n != 1 and ans == True:
print("Prime Number")
else:
print("Non Prime Number")
Output: Prime Number
function isPrime(N) {
for (let i = 2; i < N; i++) {
if (N % i === 0) {
return false;
}
}
return true;
}
let n = 11;
let ans = isPrime(n);
if (n !== 1 && ans === true) {
console.log("Prime Number");
} else {
console.log("Non Prime Number");
}
Output: Prime Number
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach
Algorithm / Intuition
Solution 2: Optimized Approach
Approach: Running the for loop till the square root of the number
A prime number is a natural number that is only divisible by 1 and by itself. Examples 1 2 3 5 7 11 13 17 19 …
Using a for loop for checking if the number is divisible by a number from 2 to its square root.
Running the for loop from 2 to the square root of the number.
And then checking if the number is divisible by the numbers from 2 to its square root.
Then, If the remainder is zero, that means it is divisible and hence not a prime number.
If the loop runs till square root and none of the numbers divided it completely. So it is the Prime number.
Code
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int N) {
for (int i = 2; i < sqrt(N); i++) {
if (N % i == 0) {
return false;
}
}
return true;
}
int main() {
int n = 11;
bool ans = isPrime(n);
if (n != 1 && ans == true) {
cout << "Prime Number";
} else {
cout << "Non Prime Number";
}
return 0;
}
Output: Prime Number
class Solution {
public static boolean isPrime(int N) {
for (int i = 2; i < Math.sqrt(N); i++) {
if (N % i == 0) {
return false;
}
}
return true;
}
public static void main(String args[]) {
int n = 20;
boolean ans = (isPrime(n));
if (n != 1 && ans == true) {
System.out.println("Prime Number");
} else {
System.out.println("Non Prime Number");
}
}
}
Output: Prime Number
from math import sqrt
def isPrime(N):
for i in range(2, int(sqrt(N))):
if N % i == 0:
return False
return True
if __name__ == "__main__":
n = 11
ans = isPrime(n)
if n != 1 and ans == True:
print("Prime Number")
else:
print("Non Prime Number")
Output: Prime Number
function isPrime(N) {
for (let i = 2; i <= Math.sqrt(N); i++) {
if (N % i === 0) {
return false;
}
}
return true;
}
let n = 11;
let ans = isPrime(n);
if (n !== 1 && ans === true) {
console.log("Prime Number");
} else {
console.log("Non Prime Number");
}
Output: Prime Number
Complexity Analysis
Time Complexity: O(√n)
Space Complexity: O(1)
Video Explanation
Special thanks to Rushikesh Adhav and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article