#=======================================================================
# 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 ) )
