Program to check if given number N is Prime or not

By Ann Roberts On Jan 4, 2023

Given a number N, the task is to check if the number is a prime number or not.

Check if given number N is Prime or not

Examples:

Input: N = 11
Output: true
Explanation: The number is not divisible by any number, other than 1 and 11 itself.

Input: N = 35
Output: false
Explanation: Apart from 1 and 35, this number is also divisible by 5 and 7.

Naive Approach (using recursion): 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++

#include <iostream>

using namespace std;

bool isPrime(int n)

{

static int i = 2;

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

return false;

}

if (n == i)

return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

int main()

{

isPrime(35) ? cout << " true\n" : cout << " false\n";

return 0;

}

Java

import java.io.*;

class GFG {

static int i = 2;

public static boolean isPrime(int n)

{

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

return false;

}

if (n == i)

return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

public static void main(String[] args)

{

if (isPrime(35)) {

System.out.println("true");

}

else {

System.out.println("false");

}

Python3

def isPrime(n, i):

if (n == 0 or n == 1):

return False

if (n == i):

return True

if (n % i == 0):

return False

i += 1

return isPrime(n, i)

if (isPrime(35, 2)):

print("true")

else:

print("false")

C#

using System;

class GFG {

static int i = 2;

static bool isPrime(int n)

{

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

return false;

}

if (n == i)

return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

static void Main()

{

if (isPrime(35)) {

Console.WriteLine("true");

}

else {

Console.WriteLine("false");

}

Javascript

<script>

function isPrime(n) {

var i = 1;

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

return false;

}

if (n == i) return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

isPrime(35) ? document.write(" true\n") : document.write(" false\n");

</script>

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient Approach: An efficient 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

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n)

{

if (n <= 1)

return false;

for (int i = 2; i <= sqrt(n); i++)

if (n % i == 0)

return false;

return true;

}

int main()

{

isPrime(11) ? cout << " true\n" : cout << " false\n";

return 0;

}

Java

import java.lang.*;

import java.util.*;

class GFG {

static boolean isPrime(int n)

{

if (n <= 1)

return false;

else if (n == 2)

return true;

else if (n % 2 == 0)

return false;

for (int i = 3; i <= Math.sqrt(n); i += 2) {

if (n % i == 0)

return false;

}

return true;

}

public static void main(String[] args)

{

if (isPrime(19))

System.out.println("true");

else

System.out.println("false");

}

Python3

from math import sqrt

def isPrime(n):

if (n <= 1):

return False

for i in range(2, int(sqrt(n))+1):

if (n % i == 0):

return False

return True

if isPrime(11):

print("true")

else:

print("false")

C#

using System;

class GFG {

static bool isPrime(int n)

{

if (n <= 1)

return false;

for (int i = 2; i < Math.Sqrt(n); i++)

if (n % i == 0)

return false;

return true;

}

static void Main()

{

if (isPrime(11))

Console.Write(" true");

else

Console.Write(" false");

}

PHP

<?php

function isPrime($n)

{

if ($n <= 1)

return false;

for ($i = 2; $i < $n; $i++)

if ($n % $i == 0)

return false;

return true;

}

if(isPrime(11))

echo("true");

else

echo("false");

?>

Javascript

function isPrime(n)

{

if (n <= 1)

return false;

for (let i = 2; i < n; i++)

if (n % i == 0)

return false;

return true;

}

isPrime(11) ? console.log(" true" + "<br>") : console.log(" false" + "<br>");

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:

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

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i <= sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

int main()

{

isPrime(11) ? cout << "true\n" : cout << "false\n";

return 0;

}

C

#include <math.h>

#include <stdio.h>

int isPrime(int n)

{

if (n <= 1)

return 0;

if (n == 2 || n == 3)

return 1;

if (n % 2 == 0 || n % 3 == 0)

return 0;

for (int i = 5; i * i <= n; i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return 0;

return 1;

}

int main()

{

if (isPrime(11) == 1)

printf("true\n");

else

printf("false\n");

return 0;

}

Java

import java.lang.*;

import java.util.*;

class GFG {

public static boolean isPrime(int n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i <= Math.sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

public static void main(String[] args)

{

if (isPrime(11)) {

System.out.println("true");

}

else {

System.out.println("false");

}

Python3

from math import * def isPrime(n):

if (n <= 1):

return "false"

if (n == 2 or n == 3):

return "true"

if (n % 2 == 0 or n % 3 == 0):

return "false"

for i in range(5, floor(sqrt(n)), 6):

if (n % i == 0 or n % (i + 2) == 0):

return "false"

return "true"

if isPrime(11):

print("true\n")

else:

print("false\n")

C#

using System;

class GFG {

public static bool isPrime(int n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i <= Math.Sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

public static void Main(String[] args)

{

if (isPrime(11)) {

Console.WriteLine("true");

}

else {

Console.WriteLine("false");

}

Javascript

function isPrime(n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (var i = 5; i <= Math.sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

isPrime(11) ? console.log("true") : console.log("false");

Time complexity: O(sqrt(n))
Auxiliary space: O(1)

Given a number N, the task is to check if the number is a prime number or not.

Check if given number N is Prime or not

Examples:

Input: N = 11
Output: true
Explanation: The number is not divisible by any number, other than 1 and 11 itself.

Input: N = 35
Output: false
Explanation: Apart from 1 and 35, this number is also divisible by 5 and 7.

Naive Approach (using recursion): 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++

#include <iostream>

using namespace std;

bool isPrime(int n)

{

static int i = 2;

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

return false;

}

if (n == i)

return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

int main()

{

isPrime(35) ? cout << " true\n" : cout << " false\n";

return 0;

}

Java

import java.io.*;

class GFG {

static int i = 2;

public static boolean isPrime(int n)

{

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

return false;

}

if (n == i)

return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

public static void main(String[] args)

{

if (isPrime(35)) {

System.out.println("true");

}

else {

System.out.println("false");

}

Python3

def isPrime(n, i):

if (n == 0 or n == 1):

return False

if (n == i):

return True

if (n % i == 0):

return False

i += 1

return isPrime(n, i)

if (isPrime(35, 2)):

print("true")

else:

print("false")

C#

using System;

class GFG {

static int i = 2;

static bool isPrime(int n)

{

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

return false;

}

if (n == i)

return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

static void Main()

{

if (isPrime(35)) {

Console.WriteLine("true");

}

else {

Console.WriteLine("false");

}

Javascript

<script>

function isPrime(n) {

var i = 1;

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

return false;

}

if (n == i) return true;

if (n % i == 0) {

return false;

}

i++;

return isPrime(n);

}

isPrime(35) ? document.write(" true\n") : document.write(" false\n");

</script>

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient Approach: An efficient 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

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n)

{

if (n <= 1)

return false;

for (int i = 2; i <= sqrt(n); i++)

if (n % i == 0)

return false;

return true;

}

int main()

{

isPrime(11) ? cout << " true\n" : cout << " false\n";

return 0;

}

Java

import java.lang.*;

import java.util.*;

class GFG {

static boolean isPrime(int n)

{

if (n <= 1)

return false;

else if (n == 2)

return true;

else if (n % 2 == 0)

return false;

for (int i = 3; i <= Math.sqrt(n); i += 2) {

if (n % i == 0)

return false;

}

return true;

}

public static void main(String[] args)

{

if (isPrime(19))

System.out.println("true");

else

System.out.println("false");

}

Python3

from math import sqrt

def isPrime(n):

if (n <= 1):

return False

for i in range(2, int(sqrt(n))+1):

if (n % i == 0):

return False

return True

if isPrime(11):

print("true")

else:

print("false")

C#

using System;

class GFG {

static bool isPrime(int n)

{

if (n <= 1)

return false;

for (int i = 2; i < Math.Sqrt(n); i++)

if (n % i == 0)

return false;

return true;

}

static void Main()

{

if (isPrime(11))

Console.Write(" true");

else

Console.Write(" false");

}

PHP

<?php

function isPrime($n)

{

if ($n <= 1)

return false;

for ($i = 2; $i < $n; $i++)

if ($n % $i == 0)

return false;

return true;

}

if(isPrime(11))

echo("true");

else

echo("false");

?>

Javascript

function isPrime(n)

{

if (n <= 1)

return false;

for (let i = 2; i < n; i++)

if (n % i == 0)

return false;

return true;

}

isPrime(11) ? console.log(" true" + "<br>") : console.log(" false" + "<br>");

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:

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

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i <= sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

int main()

{

isPrime(11) ? cout << "true\n" : cout << "false\n";

return 0;

}

C

#include <math.h>

#include <stdio.h>

int isPrime(int n)

{

if (n <= 1)

return 0;

if (n == 2 || n == 3)

return 1;

if (n % 2 == 0 || n % 3 == 0)

return 0;

for (int i = 5; i * i <= n; i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return 0;

return 1;

}

int main()

{

if (isPrime(11) == 1)

printf("true\n");

else

printf("false\n");

return 0;

}

Java

import java.lang.*;

import java.util.*;

class GFG {

public static boolean isPrime(int n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i <= Math.sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

public static void main(String[] args)

{

if (isPrime(11)) {

System.out.println("true");

}

else {

System.out.println("false");

}

Python3

from math import * def isPrime(n):

if (n <= 1):

return "false"

if (n == 2 or n == 3):

return "true"

if (n % 2 == 0 or n % 3 == 0):

return "false"

for i in range(5, floor(sqrt(n)), 6):

if (n % i == 0 or n % (i + 2) == 0):

return "false"

return "true"

if isPrime(11):

print("true\n")

else:

print("false\n")

C#

using System;

class GFG {

public static bool isPrime(int n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (int i = 5; i <= Math.Sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

public static void Main(String[] args)

{

if (isPrime(11)) {

Console.WriteLine("true");

}

else {

Console.WriteLine("false");

}

Javascript

function isPrime(n)

{

if (n <= 1)

return false;

if (n == 2 || n == 3)

return true;

if (n % 2 == 0 || n % 3 == 0)

return false;

for (var i = 5; i <= Math.sqrt(n); i = i + 6)

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

}

isPrime(11) ? console.log("true") : console.log("false");

Time complexity: O(sqrt(n))
Auxiliary space: O(1)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.