# Index of Primeby 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.
#=======================================================================
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 ) )```