Check for Prime Number

Given a number n, check whether it is a prime number or not.
Note: A prime number is a number greater than 1 that has no positive divisors other than 1 and itself.

Input: n = 7
Output: true
Explanation: 7 is a prime number because it is greater than 1 and has no divisors other than 1 and itself.

Input: n = 25
Output: false
Explanation: 25 is not a prime number because it is divisible by 5 (25 = 5 × 5), so it has divisors other than 1 and itself.

Input: n = 1
Output: false
Explanation: 1 has only one divisor (1 itself), which is not sufficient for it to be considered prime.

[Naive Approach] Basic Trial Division - O(n) Time and O(1) Space

To check if a number n is prime, first see if it's less than 2 — if so, it's not prime. Otherwise, try dividing n by every number from 2 to n - 1. If any number divides it evenly, then n is not prime. If none do, then n is a prime number.

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1)
        return false;

    // Check divisibility from 2 to n-1
    for (int i = 2; i < n; i++)
        {
            if (n % i == 0) return false;
        }

    return true;
}

int main() {
    int n = 7;
  	if(isPrime(n)) cout << "true";
  	else cout<<"false";
    return 0;
}

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int n) {
    if (n <= 1)
        return false;

    // Check divisibility from 2 to n-1
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}

int main() {
    int n = 7;
    if( isPrime(n)) printf("%s","true");
  	else printf("%s","false");
    return 0;
}

 class GfG {

    static boolean isPrime(int n) {
        if (n <= 1)
            return false;

        // Check divisibility from 2 to n-1
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;

        return true;
   }

    public static void main(String[] args) {
        int n = 7;
      	if(isPrime(n)){
        	System.out.println("true");
        }else{
          System.out.println("false");
    	}
	}
}

def isPrime(n):
    if n <= 1:
        return False

    # Check divisibility from 2 to n-1
    for i in range(2, n):
        if n % i == 0:
            return False

    return True

if __name__ == "__main__":
  n = 7
  if(isPrime(n)): 
    print("true")
  else:
    print("false")

using System;

class GfG {
    static bool isPrime(int n) {
        if (n <= 1)
            return false;

        // Check divisibility from 2 to n-1
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;

        return true;
    }

    static void Main(string[] args) {
        int n = 7;
      	if(isPrime(n))
           Console.WriteLine("true");
      	else
          Console.WriteLine("false");
    }
}

function isPrime(n) {
    if (n <= 1)
        return false;

    // Check divisibility from 2 to n-1
    for (let i = 2; i < n; i++)
        if (n % i === 0)
            return false;

    return true;
}

// Driver Code
let n = 7;
if(isPrime(n))
	console.log("true");
else
	console.log("false");

true

[Better Approach] Square Root Trial Division - O(√n) time and O(1) space

The idea is that we only need to check divisors up to √n (i.e., while i * i <= n) because divisors always come in pairs - one smaller and one larger. If a larger divisor exists beyond √n, its smaller paired divisor would have already been checked, making further checks unnecessary.

Every number n can be written as a product of two numbers: n=a×b. Here, a and b are divisors of n.

Example: n = 36

• 36 = 2 × 18 - pair (2,18)
• 36 = 3 × 12 - pair (3,12)
• 36 = 4 × 9 - pair (4,9)
• 36 = 6 × 6 - pair (6,6)

Why does this work?

Consider a number n with a pair of factors (a, b) such that a × b = n.

• If a < b, then a × a < a × b = n, which means a < √n.
• This shows that any factor larger than √n must have a corresponding factor smaller than or equal to √n.
• Therefore, it is enough to check numbers up to √n.
• If no factor ≤ √n is found, n is prime.

#include <iostream>
#include <cmath>
using namespace std;

// Function to check whether a number is prime or not
bool isPrime(int n) {

    // Numbers less than or equal to 1 are not prime
    if (n <= 1)
        return false;

    // Check divisibility from 2 to the square root of n
    for (int i = 2; i* i <=n; i++)
        if (n % i == 0)  
            return false;

    // If no divisors were found, n is prime
    return true;
}

int main() {
    int n = 7;  
  	if(isPrime(n)) cout << "true";
  	else cout<<"false";
    return 0;
}

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    // Numbers less than or equal to 1 are not prime
    if (n <= 1)
        return false;

    // Check divisibility from 2 to the square root of n
    for (int i = 2; i* i <=n; i++)
        if (n % i == 0)  
            return false;

    // If no divisors were found, n is prime
    return true;
}

int main() {
    int n = 7; 
    if( isPrime(n)) printf("%s","true");
  	else printf("%s","false");
    return 0;
}

class GfG {
    
    static boolean isPrime(int n) {
        // Numbers less than or equal to 1 are not prime
        if (n <= 1)
            return false;

        // Check divisibility from 2 to the square root of n
        for (int i = 2; i* i <=n; i++)
            if (n % i == 0) 
                return false;

        // If no divisors were found, n is prime
        return true;
    }

    public static void main(String[] args) {
        int n = 7;
      	if(isPrime(n)){
        	System.out.println("true");
        }else{
          System.out.println("false");
    	}
    }
    
}

def isPrime(n):

    # Numbers less than or equal to 1 are not prime
    if n <= 1:
        return False

    # Check divisibility from 2 to √n using i*i <= n
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    # If no divisors were found, n is prime
    return True

if __name__ == "__main__":
    n = 7
    if isPrime(n):
        print("true")
    else:
        print("false")

using System;

class GfG {
    static bool isPrime(int n) {

        // Numbers less than or equal to 1 are not prime
        if (n <= 1)
            return false;

        // Check divisibility from 2 to the square root of n
        for (int i = 2; i* i <=n; i++)
            if (n % i == 0)  
                return false;

        // If no divisors were found, n is prime
        return true;
    }

    static void Main(string[] args) {
        int n = 7;
      	if(isPrime(n))
           Console.WriteLine("true");
      	else
          Console.WriteLine("false");
    }
}

// Function to check whether a number is prime or not
function isPrime(n) {

    // Numbers less than or equal to 1 are not prime
    if (n <= 1)
        return false;

    // Check divisibility from 2 to the square root of n
    for (let i = 2; i* i <=n; i++)
        if (n % i === 0) 
            return false;

    // If no divisors were found, n is prime
    return true;
}

// Driver Code
let n = 7; 
if(isPrime(n))
	console.log("true");
else
	console.log("false");

true

[Expected Approach] Optimized Square Root Trial Division - O(√n) Time and O(1) Space

Numbers that are divisible by 2 or 3 are not prime, so we can skip them entirely. To check whether a number is prime, it is sufficient to test only the numbers of the form 6k ± 1 up to √n.

Why all prime greater than 3 can be expressed in the form 6k ± 1?

• The forms 6k, 6k+2 and 6k + 4 are all even and greater than, so they are composite. The form is a multiple of and greater than , so it is composite.
• The form 6K + 3 is a multiple of 3
• The only remaining forms are 6k + 1 and 6K + 5. The form 6K + 5 can can be rewritten as 6(k + 1) - 1, so it is covered under (6k - 1) for k = k + 1.

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
  
    // Check if n is 1 or 0
    if (n <= 1)
        return false;

    // Check if n is 2 or 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 numbers of the form 6k ± 1 up to √n
    for (int i = 5; i *i<=n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}
int main() {
    int n = 7;  
  	if(isPrime(n)) cout << "true";
  	else cout<<"false";
    return 0;
}

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
  
    // Check if n is 1 or 0
    if (n <= 1)
        return false;

    // Check if n is 2 or 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 numbers of the form 6k ± 1 up to √n
    for (int i = 5; i*i<=n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

int main() {
    int n = 7;  
    if( isPrime(n)) printf("%s","true");
  	else printf("%s","false");
    return 0;
}

class GfG {
    static boolean isPrime(int n) {
      
        // Check if n is 1 or 0
        if (n <= 1)
            return false;

        // Check if n is 2 or 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 numbers of the form 6k ± 1 up to √n
        for (int i = 5; i *i<=n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }

    public static void main(String[] args) {
        int n = 7; 
      	if(isPrime(n)){
        	System.out.println("true");
        }else{
          System.out.println("false");
    	}
    }
}

import math

def isPrime(n):

    # Check if n is 1 or 0
    if n <= 1:
        return False

    # Check if n is 2 or 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 numbers of the form 6k ± 1 up to √n
    i = 5
    while i*i<=n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

    return True

if __name__ == "__main__":
  n = 7
  if(isPrime(n)): 
    print("true")
  else:
    print("false")

using System;

class GfG {
    static bool isPrime(int n) {
      
        // Check if n is 1 or 0
        if (n <= 1)
            return false;

        // Check if n is 2 or 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 numbers of the form 6k ± 1 up to √n
        for (int i = 5; i*i<=n; i += 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }

    static void Main(string[] args) {
        int n = 7;  
      	if(isPrime(n))
           Console.WriteLine("true");
      	else
          Console.WriteLine("false");
    }
}

function isPrime(n) {
    // Check if n is 1 or 0
    if (n <= 1)
        return false;

    // Check if n is 2 or 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 numbers of the form 6k ± 1 up to √n
    for (let i = 5; i *i<=n ; i += 6)
        if (n % i === 0 || n % (i + 2) === 0)
            return false;

    return true;
}

// Driver Code
let n = 7;
if(isPrime(n))
	console.log("true");
else
	console.log("false");

true

Sieve Algorithms for Prime Number Generation

• Sieve of Eratosthenes
• Sieve of Eratosthenes in O(n) time complexity
• Segmented Sieve
• Sieve of Sundaram
• Bitwise Sieve

Prime Number Algorithms and Related Problems

• Find two distinct prime numbers with a given product
• 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
• Prime numbers and Fibonacci
• Composite Number

Some Other Primality Testing Methods

• Primality Test (Fermat Method)
• Primality Test (Miller–Rabin)
• Primality Test (Solovay-Strassen)
• Lucas Primality Test