Monday, 6 April 2015

Java program to check whether a given number is primenumber or not ?

Program to check whether a given number is primenumber or not ?

1. First of all , what is a primary number ?
A primary number is a number, which can be divided by 1 and itself only. For example, 2,3,5 and so on.

2. Now, you know what is a primary number, How can you determine the given number is primary or not?
 you already know, a prime number, consider n, can have only 2 factors at any point of time i.e 1 & n. If any number between 1 and n  divides n, then its not a prime number.
3. So, lets iterate from 2 upto n(exclusie) and check whether it can divide the number or not. If it divides then the given number is not a primary number else it is.

The program is
package numbertheory;

public class PrimeChecker {

  public static void main(String[] args) {

      System.out.println(isPrime(100000007));
  }

  public static boolean isPrime(int number) {

 for(int i = 2 ; i < number; i++) {
  if(number % i == 0) {
   System.out.println(i);
   return false;
  }
 }
 return true;
  }
}

Program explanation:

1. first consider given number as n.
2. As per algorithm, in the isPrime() method, we are dividing the given number n,with starting from 2 upto n. for example if the give number is 17, then our program starts dividing the number from 2 to 16.
3. If any number between 2 upto n, divides, then it's not a prime number, so return false from here. There is no need to run the entire for loop, because here, we already know, it is not prime number.
4. if no number is able to divide, then the for looop ends, which means it is a prime number, so return true.
5. This method is called as traial division.

An Optimized Approach:

1. you can still improve the above logic. instead of looping from 2 upto n, loop from 2 to square root of the give number (n). for example, if the given number is 25, we have to loop from 2 to 5 (inclusive). Here 5 is square root of 25.
2. The built in function to find square root of n is Math.sqrt(n);
3. The optimized code is

package numbertheory;

public class PrimeChecker {

 public static void main(String[] args) {

      System.out.println(isPrime(100000007));
 }

 public static boolean isPrime(int number) {
  int upperbound = Math.sqrt(100000007);
  for(int i = 2 ; i <= upperbound; i++) {
   if(number % i == 0) {
    System.out.println(i);
    return false;
   }
  }
  return true;
 }
}



0 comments:

Post a Comment

Note: only a member of this blog may post a comment.