## What are prime numbers?

- A prime number is a natural 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…..

Prime numbers

- In other words, the prime number is a positive integer greater than 1 that has exactly two factors, 1 and the number itself.
- There are many prime numbers, such as 2, 3, 5, 7, 11, 13, etc.
- Keep in mind that 1 cannot be either prime or composite.
- The remaining numbers, except for 1, are classified as prime and composite numbers.

DSA Self Paced Course

**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 a natural number. - Two and Three 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,

a^{n-1}≡ 1 (mod n)OR a^{n-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.

- A coprime number is always considered as a pair, whereas a prime number is considered as 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**Example of prime:**A few examples of prime numbers are 2, 3, 5, 7 and 11 etc.

**How do we check whether a number is Prime or not?**

**Naive Approach: **A naive 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)

**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

`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`

`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)

**Approach 3: **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`

`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)

**Approach 4: **To check the number is prime or not using Fermat’s little theorem with out using loop

## C++

`#include <iostream>`

`#include <cmath>`

`#include <math.h>`

`using`

`namespace`

`std;`

`bool`

`isPrime(`

`int`

`n)`

`{`

`// 0,1 and 2 will not work for fermat's little theorem`

`// Corner cases`

`if`

`(n == 0 || n == 1) {`

`return`

`false`

`;`

`}`

`if`

`( n == 2) {`

`return`

`true`

`;`

`}`

`// Checking Prime`

`else`

`{`

`int`

`p = (`

`int`

`)(`

`pow`

`(2, n-1))%n;`

`if`

`(p==1)`

`return`

`true`

`;`

`else`

`return`

`false`

`;`

`}`

`}`

`//Driver Code`

`int`

`main()`

`{`

`if`

`(isPrime(35)) {`

`cout<<`

`"Prime"`

`;`

`}`

`else`

`{`

`cout<<`

`"Not Prime"`

`;`

`}`

`return`

`0;`

`}`

## Java

`import`

`java.io.*;`

`class`

`GFG {`

`public`

`static`

`boolean`

`isPrime(`

`int`

`n)`

`{`

`// 0,1 and 2 will not work for fermat's little theorem`

`// Corner cases`

`if`

`(n == `

`0`

`|| n == `

`1`

`) {`

`return`

`false`

`;`

`}`

`if`

`( n == `

`2`

`) {`

`return`

`true`

`;`

`}`

`// Checking Prime`

`else`

`{`

`int`

`p = (`

`int`

`)(Math.pow(`

`2`

`, n-`

`1`

`))%n;`

`if`

`(p==`

`1`

`)`

`return`

`true`

`;`

`else`

`return`

`false`

`;`

`}`

`}`

`//Driver Code`

`public`

`static`

`void`

`main(String[] args)`

`{`

`if`

`(isPrime(`

`35`

`)) {`

`System.out.println(`

`"Prime"`

`);`

`}`

`else`

`{`

`System.out.println(`

`"Not Prime"`

`);`

`}`

`}`

`}`

`//contributed by raj898rki`

## Python3

`# function defination`

`def`

`isprime(n):`

`# 2 and 1 will not work for fermat's little theorem`

`if`

`n `

`=`

`=`

`2`

`and`

`n `

`=`

`=`

`1`

`:`

`print`

`(`

`'true'`

`)`

`else`

`:`

`# formula for cheacking prime or not`

`p `

`=`

`(`

`2`

`*`

`*`

`n`

`-`

`1`

`) `

`%`

`n`

`if`

`p `

`=`

`=`

`1`

`:`

`print`

`(`

`'true'`

`)`

`else`

`:`

`print`

`(`

`'false'`

`)`

`# function call`

`isprime(`

`4`

`)`

`isprime(`

`7`

`)`

`isprime(`

`2`

`)`

## C#

`using`

`System;`

`class`

`GFG {`

`public`

`static`

`bool`

`IsPrime(`

`int`

`n)`

`{`

`// 0,1 and 2 will not work for fermat's little`

`// theorem Corner cases`

`if`

`(n == 0 || n == 1) {`

`return`

`false`

`;`

`}`

`if`

`(n == 2) {`

`return`

`true`

`;`

`}`

`// Checking Prime`

`else`

`{`

`int`

`p = (`

`int`

`)(Math.Pow(2, n - 1)) % n;`

`if`

`(p == 1)`

`return`

`true`

`;`

`else`

`return`

`false`

`;`

`}`

`}`

`// Driver Code`

`static`

`void`

`Main(`

`string`

`[] args)`

`{`

`if`

`(IsPrime(35)) {`

`Console.WriteLine(`

`"Prime"`

`);`

`}`

`else`

`{`

`Console.WriteLine(`

`"Not Prime"`

`);`

`}`

`}`

`}`

`// This code is contributed by phasing17`

## Javascript

`// Function to check if a number is prime using Fermat's little theorem`

`function`

`isPrime(n) {`

`// 0,1 and 2 will not work for Fermat's little theorem`

`// Corner cases`

`if`

`(n == 0 || n == 1) {`

`return`

`false`

`;`

`}`

`if`

`(n == 2) {`

`return`

`true`

`;`

`}`

`else`

`{`

`// Checking if the number is prime`

`let p = Math.pow(2, n-1) % n;`

`if`

`(p == 1) {`

`return`

`true`

`;`

`} `

`else`

`{`

`return`

`false`

`;`

`}`

`}`

`}`

`// Driver code`

`if`

`(isPrime(35)) {`

`console.log(`

`"Prime"`

`);`

`} `

`else`

`{`

`console.log(`

`"Not Prime"`

`);`

`}`

**Output**

falsetruetrue

**Time complexity: **O(1)**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!

My Personal Notes*arrow_drop_up*

## FAQs

### What is prime number geeks for geeks practice? ›

For a given number N check if it is prime or not. **A prime number is a number which is only divisible by 1 and itself**. Example 1: Input: N = 5 Output: 1 Explanation: 5 has 2 factors 1 and 5 only.

**How do you check if a number is prime or not? ›**

How do you know a prime number? **If a number has only two factors 1 and itself, then the number is prime**. Hence, by prime factorisation of the given number, we can easily determine a prime number.

**How do you explain a prime number? ›**

Prime numbers are **numbers that have only 2 factors: 1 and themselves**. For example, the first 5 prime numbers are 2, 3, 5, 7, and 11. By contrast, numbers with more than 2 factors are call composite numbers.

**What is the logic for prime number? ›**

**A natural number is said to be prime if it is only divisible by itself and 1**. In short, a prime number has only two factors that are 1 and the number itself. The numbers that are not prime are called composite numbers. A prime number can be written as a product of only two numbers.

**Are GeeksforGeeks courses free? ›**

**FREE Online Courses By GeeksforGeeks** – Learn New Tech Skills! Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, …

**Is GeeksforGeeks certificate free? ›**

Use these free self-paced online courses to learn different programming languages, web development and more with pre-recorded video lectures by industry experts from GeeksforGeeks. **You'll also be getting a course completion certificate after completing few of these free courses**.

**Why is 11 not a prime number? ›**

Number 11 is a prime number because **it doesn't have proper factors**. In other words, the only factors of 11 are 1 and itself.

**Why 51 is not a prime number? ›**

No, 51 is not a prime number since **it has more than two factors**. The factors of 51 can be written as 1, 3, 17, 51.

**How do you teach prime numbers? ›**

The easiest way for your kid to find out if a number is prime is to **try and divide that number by all the numbers that are smaller**. If it can only be divided by 1 and itself then it's a prime number.

**Why is 69 not a prime number? ›**

The number 69 is a composite number. Its factors are 1, 3, 23, and 69. **Because 69 has more than two factors**, it is a composite number rather than a prime number.

### What is a fun fact about prime numbers? ›

**A prime number can be divided, without a remainder, only by itself and by 1**. For example, 17 can be divided only by 17 and by 1. The only even prime number is 2. All other even numbers can be divided by 2.

**Why is 27 not a prime number? ›**

Is 27 a prime number? No. **27 is divisible by other numbers (3 and 9), so it is not prime**. The factors of 27 are 1, 3, 9, and 27, so it is not prime.

**How do mathematicians find prime numbers? ›**

How to find primes. To study primes, mathematicians **strain whole numbers through one virtual mesh after another until only primes remain**. This sieving process produced tables of millions of primes in the 1800s. It allows today's computers to find billions of primes in less than a second.

**Is there a function for prime numbers? ›**

In mathematics, **the prime-counting function** is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by π(x) (unrelated to the number π).

**Why do we find prime numbers? ›**

Prime numbers are one of the most basic topics of study in the branch of mathematics called number theory. **Primes are numbers that can only be evenly divided by themselves and 1**. For example, 7 is a prime number since I'm left with a remainder or a fractional component if I divide 7 by anything other than itself or 1.

**Is GeeksforGeeks good for beginners? ›**

That being said, **GeeksforGeeks may not be the best resource for complete beginners who have little or no prior programming experience**. Some of the content on GeeksforGeeks assumes a certain level of familiarity with programming concepts and may be difficult for someone with no prior experience to understand.

**Is GeeksforGeeks Indian? ›**

Where is Geeks for Geeks 's headquarters? Geeks for Geeks is located in **Noida, Uttar Pradesh, India** .

**What is GeeksforGeeks used for? ›**

The platform was founded in 2009 by Sandeep Jain (an IIT Roorkee alumnus) as **a one-stop solution for CS/IT students to learn Programming Concepts, Data Structures & Algorithms, Coding Practice, etc**. Here, in this article, we'll let you know Why GeeksforGeeks is the most-recommended platform for all CS/IT Students.

**What is prime number in interview questions? ›**

A prime number is an integer greater than one with no positive divisors besides one and itself. For example, 17 is prime since the only factors of 17 are 17 and 1.