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.

Previous program                                                                  Next program


Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.

RELATED LINKS>



eEdit
Must read for you :