Given a number N, the task is to check if the number is a prime number or not.
Check if given number N is Prime or not
Examples:
Input: N = 11
Output: true
Explanation: The number is not divisible by any number, other than 1 and 11 itself.Input: N = 35
Output: false
Explanation: Apart from 1 and 35, this number is also divisible by 5 and 7.
Naive Approach (using recursion): To check the number is prime or not using recursion follow the below idea:
Recursion can also be used to check if a number between 2 to n – 1 divides n. If we find any number that divides, we return false.
Below is the implementation for the below idea:
C++
// C++ program to check whether a number // is prime or not using recursion #include <iostream> using namespace std; // function check whether a number // is prime or not bool isPrime(int n) { static int i = 2; // corner cases if (n == 0 || n == 1) { return false; } // Checking Prime if (n == i) return true; // base cases if (n % i == 0) { return false; } i++; return isPrime(n); } // Driver Code int main() { isPrime(35) ? cout << " true\n" : cout << " false\n"; return 0; } // This code is contributed by yashbeersingh42 |
Java
// Java program to check whether a number // is prime or not using recursion import java.io.*; class GFG { static int i = 2; // Function check whether a number // is prime or not public static boolean isPrime(int n) { // Corner cases if (n == 0 || n == 1) { return false; } // Checking Prime if (n == i) return true; // Base cases if (n % i == 0) { return false; } i++; return isPrime(n); } // Driver Code public static void main(String[] args) { if (isPrime(35)) { System.out.println("true"); } else { System.out.println("false"); } } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to check whether a number # is prime or not using recursion # Function check whether a number # is prime or not def isPrime(n, i): # Corner cases if (n == 0 or n == 1): return False # Checking Prime if (n == i): return True # Base cases if (n % i == 0): return False i += 1 return isPrime(n, i) # Driver Code if (isPrime(35, 2)): print("true") else: print("false") # This code is contributed by bunnyram19 |
C#
// C# program to check whether a number // is prime or not using recursion using System; class GFG { static int i = 2; // function check whether a number // is prime or not static bool isPrime(int n) { // corner cases if (n == 0 || n == 1) { return false; } // Checking Prime if (n == i) return true; // base cases if (n % i == 0) { return false; } i++; return isPrime(n); } static void Main() { if (isPrime(35)) { Console.WriteLine("true"); } else { Console.WriteLine("false"); } } } // This code is contributed by divyesh072019 |
Javascript
<script> // JavaScript program to check whether a number // is prime or not using recursion // function check whether a number // is prime or not function isPrime(n) { var i = 1; // corner cases if (n == 0 || n == 1) { return false; } // Checking Prime if (n == i) return true; // base cases if (n % i == 0) { return false; } i++; return isPrime(n); } // Driver Code isPrime(35) ? document.write(" true\n") : document.write(" false\n"); // This code is contributed by rdtank. </script> |
Output
false
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: An efficient solution is :
To iterate through all numbers from 2 to sqrt(n) and for every number check if it divides n. If we find any number that divides, we return false.
Below is the implementation:
C++14
// A school method based C++ program to // check if a number is prime #include <bits/stdc++.h> using namespace std; // function check whether a number // is prime or not bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to square root of n for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; } // Driver Code int main() { isPrime(11) ? cout << " true\n" : cout << " false\n"; return 0; } |
Java
// A school method based Java program to // check if a number is prime import java.lang.*; import java.util.*; class GFG { // Check for number prime or not static boolean isPrime(int n) { // Check if number is less than // equal to 1 if (n <= 1) return false; // Check if number is 2 else if (n == 2) return true; // Check if n is a multiple of 2 else if (n % 2 == 0) return false; // If not, then just check the odds for (int i = 3; i <= Math.sqrt(n); i += 2) { if (n % i == 0) return false; } return true; } // Driver code public static void main(String[] args) { if (isPrime(19)) System.out.println("true"); else System.out.println("false"); } } // This code is contributed by Ronak Bhensdadia |
Python3
# A school method based Python3 program # to check if a number is prime # function check whether a number # is prime or not # import sqrt from math module from math import sqrt def isPrime(n): # Corner case if (n <= 1): return False # Check from 2 to sqrt(n) for i in range(2, int(sqrt(n))+1): if (n % i == 0): return False return True # Driver Code if isPrime(11): print("true") else: print("false") # This code is contributed by Sachin Bisht |
C#
// A school method based C# program to // check if a number is prime using System; class GFG { // function check whether a // number is prime or not static bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to sqrt(n) for (int i = 2; i < Math.Sqrt(n); i++) if (n % i == 0) return false; return true; } // Driver Code static void Main() { if (isPrime(11)) Console.Write(" true"); else Console.Write(" false"); } } // This code is contributed by Sam007 |
PHP
<?php // A school method based PHP program to // check if a number is prime // function check whether a number // is prime or not function isPrime($n) { // Corner case if ($n <= 1) return false; // Check from 2 to n-1 for ($i = 2; $i < $n; $i++) if ($n % $i == 0) return false; return true; } // Driver Code if(isPrime(11)) echo("true"); else echo("false"); // This code is contributed by Ajit. ?> |
Javascript
// A school method based Javascript program to // check if a number is prime // function check whether a number // is prime or not function isPrime(n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (let i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Driver Code isPrime(11) ? console.log(" true" + "<br>") : console.log(" false" + "<br>"); // This code is contributed by Mayank Tyagi |
Output
true
Time Complexity: O(sqrt(n))
Auxiliary space: O(1)
Another Efficient Approach: To check whether the number is prime or not follow the below idea:
In the previous approach given if the size of the given number is too large then its square root will be also very large, so to deal with large size input we will deal with a few numbers such as 1, 2, 3, and the numbers which are divisible by 2 and 3 in separate cases and for remaining numbers, we will iterate our loop from 5 to sqrt(n) and check for each iteration whether that (iteration) or (that iteration + 2) divides n or not. If we find any number that divides, we return false.
Below is the implementation for the above idea:
C++
// A school method based C++ program to // check if a number is prime #include <bits/stdc++.h> using namespace std; // function check whether a number // is prime or not bool isPrime(int n) { // Check if n=1 or n=0 if (n <= 1) return false; // Check if n=2 or n=3 if (n == 2 || n == 3) return true; // Check whether n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check from 5 to square root of n // Iterate i by (i+6) for (int i = 5; i <= sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Driver Code int main() { isPrime(11) ? cout << "true\n" : cout << "false\n"; return 0; } // This code is contributed by Suruchi kumari |
C
// A school method based C program to // check if a number is prime #include <math.h> #include <stdio.h> // function check whether a number // is prime or not int isPrime(int n) { // Check if n=1 or n=0 if (n <= 1) return 0; // Check if n=2 or n=3 if (n == 2 || n == 3) return 1; // Check whether n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return 0; // Check from 5 to square root of n // Iterate i by (i+6) for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return 0; return 1; } // Driver Code int main() { if (isPrime(11) == 1) printf("true\n"); else printf("false\n"); return 0; } // This code is contributed by Suruchi Kumari |
Java
// Java program to check whether a number import java.lang.*; import java.util.*; class GFG { // Function check whether a number // is prime or not public static boolean isPrime(int n) { if (n <= 1) return false; // Check if n=2 or n=3 if (n == 2 || n == 3) return true; // Check whether n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check from 5 to square root of n // Iterate i by (i+6) for (int i = 5; i <= Math.sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Driver Code public static void main(String[] args) { if (isPrime(11)) { System.out.println("true"); } else { System.out.println("false"); } } } // This code is contributed by Sayan Chatterjee |
Python3
# function check whether a number # is prime or not from math import * def isPrime(n): # Check if n = 1 or n = 0 if (n <= 1): return "false" # Check if n = 2 or n = 3 if (n == 2 or n == 3): return "true" # Check whether n is divisible by 2 or 3 if (n % 2 == 0 or n % 3 == 0): return "false" # Check from 5 to square root of n # Iterate i by (i + 6) for i in range(5, floor(sqrt(n)), 6): if (n % i == 0 or n % (i + 2) == 0): return "false" return "true" if isPrime(11): print("true\n") else: print("false\n") # This code is contributed by uomkar369 |
C#
// C# program to check whether a number using System; class GFG { // Function check whether a number // is prime or not public static bool isPrime(int n) { if (n <= 1) return false; // Check if n=2 or n=3 if (n == 2 || n == 3) return true; // Check whether n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check from 5 to square root of n // Iterate i by (i+6) for (int i = 5; i <= Math.Sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Driver Code public static void Main(String[] args) { if (isPrime(11)) { Console.WriteLine("true"); } else { Console.WriteLine("false"); } } } // This code is contributed by Abhijeet // Kumar(abhijeet_19403) |
Javascript
// A school method based JS program to // check if a number is prime // function check whether a number // is prime or not function isPrime(n) { // Check if n=1 or n=0 if (n <= 1) return false; // Check if n=2 or n=3 if (n == 2 || n == 3) return true; // Check whether n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check from 5 to square root of n // Iterate i by (i+6) for (var i = 5; i <= Math.sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Driver Code isPrime(11) ? console.log("true") : console.log("false"); // This code is contributed by phasing17 |
Output
true
Time complexity: O(sqrt(n))
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
