/***************************************************************************
* Author: Isai Damier
* Title: isPrime
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
* Indicate whether the given number is prime.
*
* Sample Input: 31
* Sample Output: true
*
* 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.
*
* Alternate Algorithm:
* if(2 > num) return false;
* if(2 == num) return true;
* if(0 == num %2) return false;
* for(long i=3, sqt = (long) Math.sqrt(num); i <= sqt; i+=2 )
* if(0 == num % i)
* return false;
* return true;
*
**************************************************************************/
public boolean isPrime(int num) {
if (2 > num) {
return false;
}
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;
}
}
}
}
return primes[num];
}
import org.junit.Test;
import static org.junit.Assert.*;
public class NumbersTest {
/**
* Test of isPrime method, of class Numbers.
*/
@Test
public void testIsPrime() {
System.out.println("isPrime");
int num = 0;
Numbers primes = new Numbers();
assertFalse(primes.isPrime(0));
assertFalse(primes.isPrime(1));
assertTrue(primes.isPrime(2));
assertTrue(primes.isPrime(37));
assertFalse(primes.isPrime(58));
assertTrue(primes.isPrime(71));
assertTrue(primes.isPrime(89));
assertFalse(primes.isPrime(98));
assertTrue(primes.isPrime(157));
assertFalse(primes.isPrime(177));
assertTrue(primes.isPrime(199));
assertTrue(primes.isPrime(281));
assertFalse(primes.isPrime(417));
assertTrue(primes.isPrime(479));
assertTrue(primes.isPrime(523));
assertFalse(primes.isPrime(1089));
assertTrue(primes.isPrime(1123));
assertTrue(primes.isPrime(2029));
assertFalse(primes.isPrime(3447));
assertTrue(primes.isPrime(3539));
assertTrue(primes.isPrime(3571));
assertFalse(primes.isPrime(7917));
assertTrue(primes.isPrime(27751));
assertTrue(primes.isPrime(93563));
}
}