Skip to main content

Prime Number

Let's find if a number is prime. A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. The first few prime numbers are {2, 3, 5, 7, 11, ….}.
Here we have some solutions:

PHP: using bcmod and a for loop


function isPrimeNumber(int $num)
{
   for ($i = 2; $i <= $num - 1; $i++) {
       if (bcmod($num, $i) == 0) {
           return false;
       }
   }

   return ($num == $i);
}

var_dump( isPrimeNumber(4) ); // false
var_dump( isPrimeNumber(11) ); // true

Python: following the Wikipedia algorithm


def isPrime(n) :
 
   # Corner cases
   if (n <= 1) :
       return False
   if (n <= 3) :
       return True
 
   # This is checked so that we can skip  
   # middle five numbers in below loop
   if (n % 2 == 0 or n % 3 == 0) :
       return False
 
   i = 5
   while(i * i <= n) :
       if (n % i == 0 or n % (i + 2) == 0) :
           return False
       i = i + 6
 
   return True

# Driver Program  
if (isPrime(11)) :
   print(" true")
else :
   print(" false")
     
if(isPrime(15)) :
   print(" true")
else :  
   print(" false")

Java: using square


import java.util.Scanner;
import java.util.Scanner;

public class PrimeExample {

  public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      System.out.print("Enter a number : ");
      int n = s.nextInt();
      if (isPrime(n)) {
          System.out.println(n + " is a prime number");  
      } else {
          System.out.println(n + " is not a prime number");  
      }
  }
 
  public static boolean 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;
  }
}