Index of Prime
by Isai Damier

#=======================================================================
# 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.
#======================================================================= 
 def indexOfPrime( num ):
  ndx = -1
  # find all primes less than or equal to num
  if 2 > num:
    return ndx

  primes = [True] * ( num + 1 )
  primes[0] = primes[1] = False
  SQRT = int( sqrt( num ) )
  i = 2
  while i <= SQRT and primes[num]:
    if primes[i] :
      k = 2
      while k * i <= num:
        if primes[k * i]:
          primes[k * i] = False
        k += 1
    i += 1

  if not primes[num]:
    return ndx

  # find the index of num among primes
  for  b in primes:
    if b:
      ndx += 1

  return ndx
import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

  def testIndexOfPrime( self ):

      self.assertEquals( -1, algorithm.indexOfPrime( 0 ) )
      self.assertEquals( -1, algorithm.indexOfPrime( 1 ) )
      self.assertEquals( 0, algorithm.indexOfPrime( 2 ) )

      self.assertEquals( 11, algorithm.indexOfPrime( 37 ) )
      self.assertEquals( -1, algorithm.indexOfPrime( 58 ) )
      self.assertEquals( 19, algorithm.indexOfPrime( 71 ) )

      self.assertEquals( 23, algorithm.indexOfPrime( 89 ) )
      self.assertEquals( -1, algorithm.indexOfPrime( 98 ) )
      self.assertEquals( 36, algorithm.indexOfPrime( 157 ) )

      self.assertEquals( -1, algorithm.indexOfPrime( 177 ) )
      self.assertEquals( 45, algorithm.indexOfPrime( 199 ) )
      self.assertEquals( 59, algorithm.indexOfPrime( 281 ) )

      self.assertEquals( -1, algorithm.indexOfPrime( 417 ) )
      self.assertEquals( 91, algorithm.indexOfPrime( 479 ) )
      self.assertEquals( 98, algorithm.indexOfPrime( 523 ) )

      self.assertEquals( -1, algorithm.indexOfPrime( 1089 ) )
      self.assertEquals( 187, algorithm.indexOfPrime( 1123 ) )
      self.assertEquals( 307, algorithm.indexOfPrime( 2029 ) )

      self.assertEquals( -1, algorithm.indexOfPrime( 3447 ) )
      self.assertEquals( 494, algorithm.indexOfPrime( 3539 ) )
      self.assertEquals( 499, algorithm.indexOfPrime( 3571 ) )

      self.assertEquals( -1, algorithm.indexOfPrime( 7917 ) )
      self.assertEquals( 3027, algorithm.indexOfPrime( 27751 ) )
      self.assertEquals( 9036, algorithm.indexOfPrime( 93563 ) )