Is Prime
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: isPrime
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *  Indicate whether the given number is prime.
 *
 * Sample Input: 31
 * Sample Output: true
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(Time) = O(n log log n),
 *   where n is the number to test. You can verify this as
 *   O(Time) = n/p1+n/p2+... = n*sum(1/p) for all prime p < n^0.5
 *
 * Technical Details:  Arithmetic review:
 *   0) 0 and 1 are not prime numbers.
 *   1) The first prime number is 2.
 *   2) A number is prime if it is only divisible by itself and by 1
 *   3) If y is the square root of x (i.e. y = x^0.5); then if x is not
 *      divible by any number between 2 and y, inclusive; then x is prime.
 *
 * Alternate Algorithm:
 *   if(2 > num) return false;
 *   if(2 == num) return true;
 *   if(0 == num %2) return false;
 *   for(long i=3, sqt = (long) Math.sqrt(num); i <= sqt; i+=2 )
 *     if(0 ==  num % i)
 *       return false;
 *   return true;
 *
 **************************************************************************/ 
 public boolean isPrime(int num) {
  if (2 > num) {
    return false;
  }
  boolean[] primes = new boolean[num + 1];
  Arrays.fill(primes, true);
  primes[0] = primes[1] = false;
  int sqrt = (int) Math.sqrt(num);
  for (int i = 2; i <= sqrt && primes[num]; i++) {
    if (primes[i]) {
      for (int k = 2; k * i <= num; k++) {
        if (primes[k * i]) {
          primes[k * i] = false;
        }
      }
    }
  }
  return primes[num];
}
import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

  /**
   * Test of isPrime method, of class Numbers.
   */
  @Test
  public void testIsPrime() {
    System.out.println("isPrime");
    int num = 0;
    Numbers primes = new Numbers();
    assertFalse(primes.isPrime(0));
    assertFalse(primes.isPrime(1));
    assertTrue(primes.isPrime(2));

    assertTrue(primes.isPrime(37));
    assertFalse(primes.isPrime(58));
    assertTrue(primes.isPrime(71));

    assertTrue(primes.isPrime(89));
    assertFalse(primes.isPrime(98));
    assertTrue(primes.isPrime(157));

    assertFalse(primes.isPrime(177));
    assertTrue(primes.isPrime(199));
    assertTrue(primes.isPrime(281));

    assertFalse(primes.isPrime(417));
    assertTrue(primes.isPrime(479));
    assertTrue(primes.isPrime(523));

    assertFalse(primes.isPrime(1089));
    assertTrue(primes.isPrime(1123));
    assertTrue(primes.isPrime(2029));

    assertFalse(primes.isPrime(3447));
    assertTrue(primes.isPrime(3539));
    assertTrue(primes.isPrime(3571));

    assertFalse(primes.isPrime(7917));
    assertTrue(primes.isPrime(27751));
    assertTrue(primes.isPrime(93563));
  }
}