Index of Prime
by Isai Damier, Android Engineer @ Google

/***********************************************************************
 * Author: Isai Damier
 * Title: Index of Prime
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *  Indicate the index of the given prime number. If the number is not
 *  prime, return -1.
 *
 * Sample Input: 31
 * Sample Output: 10
 *
 * 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.
 *
 * After finding all the prime numbers between 2 and n; simply loop
 * through the list, counting the number of primes.
 *
 **********************************************************************/ 
 public int indexOfPrime(int num) {
  int ndx = -1;
  //find all primes less than or equal to num
  if (2 > num) {
    return ndx;
  }
  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;
        }
      }
    }
  }
  if (!primes[num]) {
    return ndx;
  }
  //find the index of num among primes
  for (boolean b : primes) {
    if (b) {
      ndx++;
    }
  }
  return ndx;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

/**
   * Test of indexOfPrime method, of class Numbers.
   */
  @Test
  public void testIndexOfPrime() {
    System.out.println("indexOfPrime");
    int num = 0;
    Numbers primes = new Numbers();
    assertEquals(-1,primes.indexOfPrime(0));
    assertEquals(-1,primes.indexOfPrime(1));
    assertEquals(0,primes.indexOfPrime(2));

    assertEquals(11,primes.indexOfPrime(37));
    assertEquals(-1,primes.indexOfPrime(58));
    assertEquals(19,primes.indexOfPrime(71));

    assertEquals(23,primes.indexOfPrime(89));
    assertEquals(-1,primes.indexOfPrime(98));
    assertEquals(36,primes.indexOfPrime(157));

    assertEquals(-1,primes.indexOfPrime(177));
    assertEquals(45,primes.indexOfPrime(199));
    assertEquals(59,primes.indexOfPrime(281));

    assertEquals(-1,primes.indexOfPrime(417));
    assertEquals(91,primes.indexOfPrime(479));
    assertEquals(98,primes.indexOfPrime(523));

    assertEquals(-1,primes.indexOfPrime(1089));
    assertEquals(187,primes.indexOfPrime(1123));
    assertEquals(307,primes.indexOfPrime(2029));

    assertEquals(-1,primes.indexOfPrime(3447));
    assertEquals(494,primes.indexOfPrime(3539));
    assertEquals(499,primes.indexOfPrime(3571));

    assertEquals(-1,primes.indexOfPrime(7917));
    assertEquals(3027,primes.indexOfPrime(27751));
    assertEquals(9036,primes.indexOfPrime(93563));
  }
}