A prime number is a whole number greater than 1, which is only divisible by 1 and itself. First few prime numbers are : 2 3 5 7 11 13 17 19 23 …..
Some interesting fact about Prime numbers
- Two is the only even Prime number.
- Every prime number can represented in form of 6n+1 or 6n-1 except 2 and 3, where n is natural number.
- Two and Three are only two consecutive natural numbers which are prime too.
- Goldbach Conjecture: Every even integer greater than 2 can be expressed as the sum of two primes.
- GCD of all other natural numbers with a prime is always one.
- 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.
How we check whether a number is Prime or not?
- Naive solution.
A naive solution is to iterate through all numbers from 2 to n-1 and for every number check if it divides n. If we find any number that divides, we return false.
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)
{
// Corner case
if
(n <= 1)
return
false
;
// Check from 2 to n-1
for
(
int
i = 2; i < n; i++)
if
(n % i == 0)
return
false
;
return
true
;
}
// Driver Program
int
main()
{
isPrime(11) ? cout <<
" true "
:
cout <<
" false "
;
return
0;
}
Java
// A school method based Java program to
// check if a number is prime
import
java.util.*;
class
GFG {
// function check whether a number
// is prime or not
static
boolean
isPrime(
int
n)
{
// Corner case
if
(n <=
1
)
return
false
;
// Check from 2 to n-1
for
(
int
i =
2
; i < n; i++)
if
(n % i ==
0
)
return
false
;
return
true
;
}
/* Driver program */
public
static
void
main(String[] args)
{
if
(isPrime(
11
))
System.out.println(
" true"
) ;
else
System.out.println(
" false"
);
}
}
// This code is contributed by Arnav Kr. Mandal
Python3
# A school method based Python3 program
# to check if a number is prime
# function check whether a number
# is prime or not
def
isPrime(n):
# Corner case
if
(n <
=
1
):
return
False
# Check from 2 to n-1
for
i
in
range
(
2
, n):
if
(n
%
i
=
=
0
):
return
False
return
True
# Driver Program
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 n-1
for
(
int
i = 2; i < 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.
?>
Output :
Time complexity :O(n)True
- Efficient solutions
Algorithms to find all prime number smaller 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 given product
- Print all prime numbers less than or equal to N
- Recursive program for prime number
- Find two prime numbers with 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!
leave a comment
0 Comments