/***********************************************************************
* 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));
}
}