All Primes
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: All Primes
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *  Given a number n, return all prime numbers less than or equal to n.
 *
 * Sample Input: 35
 * Sample Output: {2,3,5,7,11,13,17,19,23,29,31}
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(Time) = O(n log log n),
 *   where n is the max 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
 *
 * Approach:
 *   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^2 = x); then if x is not
 *      divisible by any number between 2 and y inclusive, then x is prime.
 *
 *   This is an "innocent until proven guilty" algorithm that capitalizes on
 *   the above arithmetic facts to find all primes between 2 and n. In the
 *   innocent until proven guilty paradigm, all candidates start out as
 *   winners. Then through a rigorous process, the algorithm winnows the
 *   faulty candidates until the elite is left. Known as the sieve of
 *   Eratosthenes, there are a number of ways to implement the set of
 *   arithmetic rules above into an algorithm. The following is easy to
 *   understand.
 *
 *   0] Declare a bit vector and initialize all the keys from 0 to
 *      x with the value 'true' -- making them all primes.
 *   1] For keys 0 and 1, set the values to false
 *   2] For each number n between 2 and x, set all multiples of n to false.
 *   3] Group together all keys whose values are still true and
 *      return that group.
 *
 * There are a number of ways to improve the time complexity of this
 * program, such as considering only odd numbers as opposed to all
 * numbers between 2 and n.
 **************************************************************************/ 
 public List<Integer> allPrimes(int max) {
  if (2 > max) {
    return null;
  }
  boolean[] primes = new boolean[max + 1];
  Arrays.fill(primes, true);
  primes[0] = primes[1] = false;
  for (int i = 2, sqrt = (int) Math.sqrt(max); i <= sqrt; i++) {
    if (primes[i]) {
      for (int k = 2; k * i <= max; k++) {
        if (primes[k * i]) {
          primes[k * i] = false;
        }
      }
    }
  }
  List<Integer> result = new ArrayList<Integer>();
  for (int i = 2; i <= max; i++) {
    if (primes[i]) {
      result.add(i);
    }
  }
  return result;
}

import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

  /**
   * Test of allPrimes method, of class Numbers.
   */
  @Test
  public void testAllPrimes() {
    System.out.println("allPrimes");
    int max = 0;
    Numbers primes = new Numbers();
    List<Integer> expected = Arrays.asList(
        new Integer[] {2,3,5,7,11,13,17,19,23,29});
    assertTrue(expected.equals(primes.allPrimes(30)));

    expected = Arrays.asList(
        new Integer[] {2,3,5,7,11,13,17,19,23,29,31});
    assertTrue(expected.equals(primes.allPrimes(31)));

    expected = Arrays.asList(
        new Integer[] {2,3,5,7,11,13,17,19,23,29,31,37});
    assertTrue(expected.equals(primes.allPrimes(40)));
  }
}