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.
Memoization. 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.
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
Summary. 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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Jan 20, 2024 (edit).