A simple algorithm

exercise No. 157

Testing an implementation

Q:

Consider the following method aimed to test whether a given long number is prime or not: 

/**
 * Test, whether a given number is prime.
 * @param candidate The number to be assessed
 * @return true if candidate is prime, false otherwise
 * <dl>
 *   <dt>Precondition:</dt>
 *   <dd>2 &lt;= candidate</dd>
 * </dl>
 **/
public static boolean isPrime(final long candidate) {
  for (long i = 2; i * i < candidate; i++) { // Just test up to square
    if (0 == candidate % i) {                 // root of candidate.
      return false;
    }
  }
  return true;
}

  1. Write a concise test which tests the above method for all numbers within the range [2, 100]. You need to know all prime numbers from this set in order to implement a complete test for both directions “is prime” and “is not prime”.

  2. In case you find errors correct them.

  3. Write a method which tests prime number candidates up to an arbitrary limit (say limit == 10000) and returns the number of primes within [2, limit]. Measure this method's execution time. You may want to consult System.currentTimeMillis() or System.nanoTime() for that purpose.

A:

  1. We want to test whether our boolean isPrime(final long candidate) method classifies prime numbers as such and whether this message is able to tell non-primes as well. We achieve this by defining a boolean array having indexes ranging from 0 to 100 (inclusive). We then:

    • Set all array values to false

    • Set all array values to true if their index is a prime number. This of course requires to know all prime numbers below 100.

    This array then allows us to test our method for correctness for values up to 100: 

    public class TestPrimes {

  @Test
  public void primeTest() {
    final int[] primeNumbers = { 2,  3,  5,  7, 11, 13, 17, 19, 23,
                                31, 37, 41, 43, 47, 53, 59, 29,
                                61, 67, 71, 73, 79, 83, 89, 97};

    final boolean[] isPrime = new boolean[101]; //Testing 2, 3, 4, .., 99, 100
    for (int i = 2; i <= 100; i++) {
      isPrime[i] = false;
    }
    for (final int prime: primeNumbers) {
      isPrime[prime] = true;
    }
    for (int i = 2; i <= 100; i++) {
      assertEquals("Index=" + i , isPrime[i], PrimeNumbers.isPrime(i));
    }
  }

  2. Executing this test yields an error at index 49. This is due to the chosen limit i * i < candidate in: 

    public static boolean isPrime(final long candidate) {
  for (long i = 2; i * i < candidate; i++) {
    ...

    This is wrong: Having candidate == 49 the last value of i to be considered will be 6. So the required test 49 % 7 will never be executed thus erroneously returning true. We have to modify the loop's limit slightly by using i * i <= candidate instead: 

    public static boolean isPrime(final long candidate) {
  for (long i = 2; i * i <= candidate; i++) {
     ...

    This way 49 % 7 will be evaluated to zero thus returning false and thereby categorizing 49 as a non-prime number.

  3. Executing main() allows for estimating the prime number computing performance: 

    Found 664579 prime numbers within 15.136 seconds.
Prev  Up  Next
Prime numbers revisited  Home  Improving performance