### A simple algorithm

No. 153

#### 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 sub directory P/Sd1/Prime/V1 below lecture notes' source code root, see hints regarding import. Online browsing of API and implementation. 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)); } } 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.