Friday, September 21, 2012

Optimized Trial Division Prime Number Checking

Wikipedia definition of a prime number: "A prime number (or a prime) is a natural number greater than 1 that has no positive divisorsother than 1 and itself."  On that page, if you scroll down a bit, you'll see "Testing Primality...".  The following is a little 'Trial Division' method of determining if an entered int is a prime.  It is obviously limited to small numbers (java int), and it is not as efficient as the 'deterministic' algorithms mentioned on that page (which are O(logi(n) [iterative logarithmic], better than the presented code's ~ O(n1/2)).  It does, however, skip over all even and numbers divisible by 3 (other than 2 and 3, which are valid input).


import java.util.Scanner;

/**
 * Checks if a given number is prime
 @author sshakil
 *
 */
public class PrimeNumberChecker {

  public static void main(String[] args) {
    
    Scanner input = new ScannerSystem.in )
    int a;
    do {
      a = input.nextInt();
      System.out.println(isPrime(a));
    while(a!=0);
  }
  
  private static boolean isPrime(int a){
    if (a!= && a!=&& (a%2==0  || a%3==0))
      return false;

    int sqrRoot = (intMath.ceil(Math.sqrt(a));
    int i = 2;
    for (; i <= sqrRoot && i%!=; i++) {
      if(a%i == 0)
        return false;
    }
    return true;
  }

}

No comments:

Post a Comment