Java - Prime Number Method

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.

for

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

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.

HashMap

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.