Last Updated : 29 Mar, 2024
Improve
What are Prime Numbers?
A prime number is defined as a natural number greater than 1 and is divisible by only 1 and itself.
In other words, the prime number is a positive integer greater than 1 that has exactly two factors, 1 and the number itself. First few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 . . .
Note: 1 is not either prime or composite. The remaining numbers, except for 1, are classified as prime and composite numbers.
Prime numbers
Some interesting facts about Prime Numbers:
- Except for 2, which is the smallest prime number and the only even prime number, all prime numbers are odd numbers.
- Every prime number can be represented in form of 6n + 1 or 6n – 1 except the prime numbers 2 and 3, where n is any natural number.
- 2 and 3 are only two consecutive natural numbers that are prime.
- Goldbach Conjecture: Every even integer greater than 2 can be expressed as the sum of two primes.
- Wilson Theorem: Wilson’s theorem states that a natural number p > 1 is a prime number if and only if
(p – 1) ! ≡ -1 mod p
OR,
(p – 1) ! ≡ (p-1) mod p
- Fermat’s Little Theorem: If n is a prime number, then for every a, 1 ≤ a < n,
an-1 ≡ 1 (mod n)
OR,
an-1 % n = 1
- Prime Number Theorem: The probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or to the logarithm of n.
- Lemoine’s Conjecture: Any odd integer greater than 5 can be expressed as a sum of an odd prime (all primes other than 2 are odd) and an even semiprime. A semiprime number is a product of two prime numbers. This is called Lemoine’s conjecture.
Properties of Prime Numbers:
- Every number greater than 1 can be divided by at least one prime number.
- Every even positive integer greater than 2 can be expressed as the sum of two primes.
- Except 2, all other prime numbers are odd. In other words, we can say that 2 is the only even prime number.
- Two prime numbers are always coprime to each other.
- Each composite number can be factored into prime factors and individually all of these are unique in nature.
Prime Numbers and Co-prime numbers:
It is important to distinguish between prime numbers and co-prime numbers. Listed below are the differences between prime and co-prime numbers.
- Coprime numbers are always considered as a pair, whereas a prime number is a single number.
- Co-prime numbers are numbers that have no common factor except 1. In contrast, prime numbers do not have such a condition.
- A co-prime number can be either prime or composite, but its greatest common factor (GCF) must always be 1. Unlike composite numbers, prime numbers have only two factors, 1 and the number itself.
- Example of co-prime: 13 and 15 are co-primes. The factors of 13 are 1 and 13 and the factors of 15 are 1, 3 and 5. We can see that they have only 1 as their common factor, therefore, they are coprime numbers.
- Example of prime: A few examples of prime numbers are 2, 3, 5, 7 and 11 etc.
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
- Primality Test | Set 1 (Introduction and School Method)
- Primality Test | Set 2 (Fermat Method)
- Primality Test | Set 3 (Miller–Rabin)
- Primality Test | Set 4 (Solovay-Strassen)
- Lucas Primality Test
Algorithms to find all prime numbers smaller than the N.
- Sieve of Eratosthenes
- Sieve of Eratosthenes in 0(n) time complexity
- Segmented Sieve
- Sieve of Sundaram
- Bitwise Sieve
- Recent Articles on Sieve!
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 – GeeksforGeeks
- Program for Goldbach’s Conjecture
- Prime numbers and Fibonacci
- Composite Number
- Recent Articles on Prime Numbers!
Like Article
Suggest improvement
Next
Introduction to Primality Test and School Method
Share your thoughts in the comments