Primes

Sometimes prime numbers are helpful in Java programs. With them, we can size a hash table so that fewer collisions occur. We check for primes by trying to detect divisors.

It is easy to detect a prime number by trying repeatedly to divide it. With memoization, though, we can cache which numbers are prime.

Example

This Java example introduces an isPrime method. It first checks for even numbers, which (other than 2) are never primes. It then loops and tries to divide with modulo.

Start The bitwise AND in isPrime() returns 0 if a number is evenly divisible. This can detect a possible prime factor.

Next We test some ranges of numbers for primes. We print the first primes—the primes 2, 3, 5, 7, are well-known.

public class Program {

    public static boolean isPrime(int candidate) {
        // All even numbers except 2 are not primes.
        if ((candidate & 1) == 0) {
            if (candidate == 2) { // Two is prime.
            return true;
        } else {
            return false;
        }
    }
    // Search for prime numbers of the candidate.
    // ... Primes are odd, smaller than the candidate.
    // ... And a modulo division returns 0.
    for (int i = 3; (i * i) <= candidate; i += 2) {
        if ((candidate % i) == 0) {
            return false;
        }
    }
    return candidate != 1;
}

public static void main(String[] args) {

    // Test first 100 numbers for primes.
    for (int test = 0; test < 100; test++) {
        if (isPrime(test)) {
            System.out.println(test);
        }
    }
    // Test larger numbers.
    for (int test = 10000; test < 10100; test++) {
        if (isPrime(test)) {
            System.out.println(test);
        }
    }
}
}2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
10007
10009
10037
10039
10061
10067
10069
10079
10091
10093
10099

Memoize primes

The word memoize is not misspelled. It means to "remember" or store the result of a method in a "memo." Here we use HashMap to cache primes.

Start IsPrime() is the same method as described in the previous example. It returns a boolean value.

Next IsPrimeMemoized is a wrapper for isPrime. It uses a HashMap to see if a number's status has already been recorded.

Finally We invoke isPrimeMemoized twice. It internally calls isPrime once: the memoized result is used the second time.

import java.util.HashMap;

public class Program {

    public static boolean isPrime(int candidate) {
        // This is the same method as described above.
        if ((candidate & 1) == 0) {
            if (candidate == 2) {
                return true;
            } else {
                return false;
            }
        }
        for (int i = 3; (i * i) <= candidate; i += 2) {
            if ((candidate % i) == 0) {
                return false;
            }
        }
        return candidate != 1;
    }

    static HashMap<Integer, Boolean> primes = new HashMap<>();

    public static boolean isPrimeMemoized(int candidate) {
        // Try to use the HashMap to see if a number is a prime.
        if (primes.containsKey(candidate)) {
            System.out.println("Memoized prime result");
            return primes.get(candidate);
        }
        // Record our prime status in the HashMap.
        boolean result = isPrime(candidate);
        primes.put(candidate, result);
        return result;
    }

    public static void main(String[] args) {
        // Detect prime numbers with memoized method.
        boolean value = isPrimeMemoized(10007);
        System.out.println(value);
        value = isPrimeMemoized(10007);
        System.out.println(value);
    }
}true
Memoized prime result
true

To test for primes, we use many program constructs. We use a bitwise "and" to test for even numbers. And we use a loop, with a modulo division, to test for prime factors.