How to check whether a number is Prime or not?
Naive Approach: The naive approach is to
Iterate from 2 to (n-1) and check if any number in this range divides n. If the number divides n, then it is not a prime number.
Time Complexity: O(N)
Auxiliary Space: O(1)
Naive approach (recursive): 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 of the above 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 var i = 2; function isPrime(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 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) if we consider the recursion stack. Otherwise, it is O(1).
Efficient Approach: An efficient solution is to:
Iterate through all numbers from 2 to ssquare root of n and for every number check if it divides n [because if a number is expressed as n = xy and any of the x or y is greater than the root of n, the other must be less than the root value]. 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 # import sqrt from math module from math import sqrt # Function check whether a number # is prime or not 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 __name__ == '__main__': 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 |
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") : console.log(" false"); // This code is contributed by Mayank Tyagi |
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. ?> |
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:
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. Iterate from 5 to sqrt(n) and check for each iteration whether (that value) or (that value + 2) divides n or not and increment the value by 6 [because any prime can be expressed as 6n+1 or 6n-1]. 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
import math def is_prime(n: int) -> bool: # 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, int(math.sqrt(n))+1, 6): if n % i == 0 or n % (i + 2) == 0: return "false" return "true" if __name__ == '__main__': print(is_prime(11)) |
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)
Efficient solutions
Algorithms to find all prime numbers smaller than the N.
More problems related to Prime number
- Find two distinct prime numbers with a given product
- Print all prime numbers less than or equal to N
- Recursive program for prime number
- Find two prime numbers with a given sum
- Find the highest occurring digit in prime numbers in a range
- Prime Factorization using Sieve O(log n) for multiple queries
- Program to print all prime factors of a given number
- Least prime factor of numbers till n
- Prime factors of LCM of array elements – w3wiki
- Program for Goldbach’s Conjecture
- Prime numbers and Fibonacci
- Composite Number
- Recent Articles on Prime Numbers!