### A simple algorithm No. 161

#### 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 *
*
Precondition:
*
2 <= candidate
*
**/ 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; } 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”. In case you find errors correct them. 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: Maven module source code available at P/Sd1/Prime/V1. 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; //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)); } } 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. Executing main() allows for estimating the prime number computing performance: Found 664579 prime numbers within 15.136 seconds.