### Prime number in java

In this programming tutorial we will write a program to found out number is prime or not in java.

What is prime number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

I have seen at many places iteration starting from i=2 to i<=n/2 which offers time complexity of O(n/2).
But, we will start iterating from i=2 to i<=Math.sqrt(n).
Q. why i<=Math.sqrt(n)?
A.It will help us in reducing time complexity from O(n/2) to O(N).

Must read: Find number is binary or not in java.

Complexity of program to found out number is prime or not in java>
O(N )

Full Program/SourceCode/Example to found out number is prime or not in java >
 /** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */ public class PrimeNumberExample {    public static void main(String[] args) {                     int n=11;           System.out.println(isPrimeNumber(n)? n+" is prime number." : n+" is not prime number.");           n=12;           System.out.println(isPrimeNumber(n)? n+" is prime number." : n+" is not prime number.");           n=13;           System.out.println(isPrimeNumber(n)? n+" is prime number." : n+" is not prime number.");           n=14;           System.out.println(isPrimeNumber(n)? n+" is prime number." : n+" is not prime number.");    }       /**    * returns true if number is prime.    */    public static boolean isPrimeNumber(int n){                            for(int i=2;i<=Math.sqrt(n);i++){                  if(n%i==0){                        return false;                  }           }           return true;  //means number wasn't divisible by any of the number, it's a prime number.    } } /*OUTPUT 11 is prime number. 12 is not prime number. 13 is prime number. 14 is not prime number. */

Complexity comparison of program when we iterate till i<=Math.sqrt(n) and i<=n/2 >

 when we iterate till  i<=Math.sqrt(n) when we iterate till  i<=n/2 n When, i=2 to i<=Math.sqrt(n). Time complexity = O(√ N ) when, i=2 to i<=n/2 Time complexity = O( n/2 ) 11 i=2 to i<=3 [max two executions] i=2 to i<=5 [max 4 execution] 21 i=2 to i<=4 [max three executions] i=2 to i<=10 [max 9 execution] GOOD Performance. POOR performance.

In this programming tutorial we learned how to Write a program to found out number is prime or not in java.

Having any doubt? or you you liked the tutorial! Please comment in below section.