Posted on by Kalkicode
Code Number

Check if a number is prime or not

Introduction:

In mathematics, a prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words, a prime number has only two factors: 1 and itself. Determining whether a given number is prime or not is a common problem in mathematics and computer science.

Problem Statement:

We want to write a program that checks whether a given number is prime or not. The program should take an input number and output whether it is a prime number or not.

Example:

Let's consider an example to understand the concept better. Suppose we have a number 37. We want to check if it is prime or not.

Algorithm:

The algorithm to determine whether a number is prime or not can be explained as follows:

  1. Start by checking if the number is less than or equal to 1. If it is, then it is not prime.
  2. Check for some base cases where the number is known to be prime (e.g., 2, 3, 5). Return true if the number matches any of these cases.
  3. Iterate from n/2 to 2 and check if the number is divisible by any of these values. If it is divisible, then it is not prime.
  4. If none of the above conditions are satisfied, then the number is prime.

Pseudocode:

function is_prime(n):
    if n <= 1:
        return false
    if n is 2 or 3 or 5:
        return true
    for i from n/2 to 2:
        if n is divisible by i:
            return false
    return true

function prime_number(number):
    if is_prime(number):
        print number, "is a prime number"
    else:
        print number, "is not a prime number"

Explanation:

The program starts by defining a function is_prime that takes a number n as input. It checks if the number is less than or equal to 1 and returns false in such cases. Then it checks for the base cases where the number is known to be prime (2, 3, and 5) and returns true if the number matches any of these cases. Next, it iterates from n/2 to 2 and checks if the number is divisible by any of these values. If it is divisible, then it returns false, indicating that the number is not prime. If none of the conditions are satisfied, it returns true, indicating that the number is prime.

The prime_number function takes a number as input and calls the is_prime function. If the is_prime function returns true, it prints that the number is a prime number; otherwise, it prints that the number is not prime.

Code Solution

Here given code implementation process.

//C Program
//Check if a number is prime or not
#include <stdio.h>

int is_prime(int n)
{
  if(n<=1)
  {
    return 0;
  }
  //Base case
  if(n==2 || n ==3 || n==5)
  {
    return 1;
  }
  //Check divisibility of a number
  for (int i = n/2; i > 1 ; --i)
  {
    if(n%i == 0)
    {
      return 0;
    }
  }
  
  return 1;
}

void prime_number(int number)
{


  if(is_prime(number)==1)
  {
    printf("%d is a prime number\n",number );
  }
  else
  {
    printf("%d not a prime number\n",number );
  }
  
}


int main()
{
  prime_number(37);
  prime_number(46);
  return 0;
}

Output

37 is a prime number
46 not a prime number
#include<iostream>

using namespace std;
/*
 C++ Program
 Check if a number is prime or not
*/
class MyNumber {
	public:
		bool is_prime(int n) {
			if (n <= 1) {
				return false;
			}
			//Base case

			if (n == 2 || n == 3 || n == 5) {
				return true;
			}
			for (int i = n / 2; i > 1; --i) {
				//Check divisibility of a number

				if (n % i == 0) {
					return false;
				}
			}
			return true;
		}
	void prime_number(int number) {
		if (this->is_prime(number)) {
			cout << number << " is a prime number\n";
		} else {
			cout << number << " number not a prime number\n";
		}
	}
};
int main() {
	MyNumber obj;
	//Test case
	obj.prime_number(37);
	obj.prime_number(46);
	return 0;
}

Output

37 is a prime number
46 number not a prime number
/*
  Java Program
  Check if a number is prime or not
*/

public class MyNumber {


  
  public boolean is_prime(int n)
  {
    if(n<=1)
    {
      return false;
    }
    //Base case
    if(n==2 || n ==3 || n==5)
    {
      return true;
    }
    
    for (int i = n/2; i > 1 ; --i)
    {
      //Check divisibility of a number
      if(n%i == 0)
      {
        return false;
      }
    }
    
    return true;
  }

  public void prime_number(int number)
  {


    if(is_prime(number))
    {
      System.out.print(number+" is a prime number\n");
    }
    else
    {
      System.out.print(number+" number not a prime number\n");
    }
    
  }


  public static void main(String[] args) {

    MyNumber obj = new MyNumber();
    //Test case
    obj.prime_number(37);
    obj.prime_number(46);

  }
}

Output

37 is a prime number
46 number not a prime number
/*
  C# Program
  Check if a number is prime or not
*/
using System;
public class MyNumber {



	public Boolean is_prime(int n) {
		if (n <= 1) {
			return false;
		}
		//Base case
		if (n == 2 || n == 3 || n == 5) {
			return true;
		}

		for (int i = n / 2; i > 1; --i) {
			//Check divisibility of a number
			if (n % i == 0) {
				return false;
			}
		}

		return true;
	}

	public void prime_number(int number) {


		if (is_prime(number)) {
			Console.Write(number + " is a prime number\n");
		} else {
			Console.Write(number + " number not a prime number\n");
		}

	}


	public static void Main(String[] args) {

		MyNumber obj = new MyNumber();
		//Test case
		obj.prime_number(37);
		obj.prime_number(46);

	}
}

Output

37 is a prime number
46 number not a prime number
# Python 3 Program
# Check if a number is prime or not
class MyNumber :
	def is_prime(self, n) :
		if (n <= 1) :
			return False
		
		#Base case
		if (n == 2 or n == 3 or n == 5) :
			return True
		
		i = n / 2
		while (i > 1) :
			#Check divisibility of a number
			if (n % i == 0) :
				return False
			
			i -= 1
		
		return True
	
	def prime_number(self, number) :
		if (self.is_prime(number)) :
			print(number ," is a prime number\n")
		else :
			print(number ," number not a prime number\n")
		
	

def main() :
	obj = MyNumber()
	obj.prime_number(37)
	obj.prime_number(46)


if __name__ == "__main__":
	main()

Output

37 is a prime number
46 number not a prime number
# Ruby Program 
# Check if a number is prime or not
class MyNumber 
	def is_prime(n) 
		if (n <= 1) 
			return false
		end
		#Base case

		if (n == 2 or n == 3 or n == 5) 
			return true
		end
		i = n / 2
		while (i > 1) 
			#Check divisibility of a number

			if (n % i == 0) 
				return false
			end
			i -= 1
		end
		return true
	end
	def prime_number(number) 
		if (self.is_prime(number)) 
			print(number ," is a prime number\n")
		else 
			print(number ," number not a prime number\n")
		end
	end
end
def main() 
	obj = MyNumber.new()
	obj.prime_number(37)
	obj.prime_number(46)
end
main()

Output

37 is a prime number
46 number not a prime number
/*
 Scala Program
 Check if a number is prime or not
*/
class MyNumber {
	def is_prime(n: Int): Boolean = {
		if (n <= 1) {
			return false;
		}
		//Base case

		if (n == 2 || n == 3 || n == 5) {
			return true;
		}
		var i: Int = n / 2;
		while (i > 1) {
			//Check divisibility of a number

			if (n % i == 0) {
				return false;
			}
			i -= 1;
		}
		return true;
	}
	def prime_number(number: Int): Unit = {
		if (this.is_prime(number)) {
			print(s" $number is a prime number\n");
		} else {
			print(s" $number not a prime number\n");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		var obj: MyNumber = new MyNumber();obj.prime_number(37);obj.prime_number(46);
	}
}

Output

 37 is a prime number
 46 not a prime number
/*
  Swift 4 Program
  Check if a number is prime or not
*/
class MyNumber {
	func is_prime(_ n: Int) -> Bool {
		if (n <= 1) {
			return false;
		}
		//Base case

		if (n == 2 || n == 3 || n == 5) {
			return true;
		}
		var i: Int = n / 2;
		while (i > 1) {
			//Check divisibility of a number

			if (n % i == 0) {
				return false;
			}
			i -= 1;
		}
		return true;
	}
	func prime_number(_ number: Int) {
		if (self.is_prime(number)) {
			print(number ," is a prime number");
		} else {
			print(number ," number not a prime number");
		}
	}
}
func main() {
	let obj: MyNumber = MyNumber();
	obj.prime_number(37);
	obj.prime_number(46);
}
main();

Output

37  is a prime number
46  number not a prime number
<?php
/*
  Php Program
  Check if a number is prime or not
*/
class MyNumber {
	public 	function is_prime($n) {
		if ($n <= 1) {
			return false;
		}
		//Base case

		if ($n == 2 || $n == 3 || $n == 5) {
			return true;
		}
		for ($i = intval($n / 2); $i > 1; --$i) {
			//Check divisibility of a number

			if ($n % $i == 0) {
				return false;
			}
		}
		return true;
	}
	public 	function prime_number($number) {
		if ($this->is_prime($number)) {
			echo($number ." is a prime number\n");
		} else {
			echo($number ." number not a prime number\n");
		}
	}
};

function main() {
	$obj = new MyNumber();
	//Test case

	$obj->prime_number(37);
	$obj->prime_number(46);
}
main();

Output

37 is a prime number
46 number not a prime number
/*
 Node Js Program
 Check if a number is prime or not
*/
class MyNumber {
	is_prime(n) {
		if (n <= 1) {
			return false;
		}
		//Base case

		if (n == 2 || n == 3 || n == 5) {
			return true;
		}
		for (var i = parseInt( n / 2); i > 1; --i) {
			//Check divisibility of a number

			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
	prime_number(number) {
		if (this.is_prime(number)) {
			process.stdout.write(number + " is a prime number\n");
		} else {
			process.stdout.write(number + " number not a prime number\n");
		}
	}
}

function main(args) {
	var obj = new MyNumber();
	//Test case
	obj.prime_number(37);
	obj.prime_number(46)
}
main();

Output

37 is a prime number
46 number not a prime number

Resultant Output:

When we run the program with the input numbers 37 and 46, we get the following output:

37 is a prime number

46 is not a prime number

Explanation of Output:

In the given example, we checked whether the numbers 37 and 46 are prime or not. The output indicates that 37 is a prime number, while 46 is not a prime number.

Time Complexity:

The time complexity of the algorithm is approximately O(n/2), where n is the given number. This is because we iterate from n/2 to 2 to check for divisibility. Therefore, the time complexity can be simplified as O(n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment