HomeSearch

Java Prime Number Method

This Java example tests for prime numbers using a for-loop and if-statements. It introduces an isPrime method.
Primes. Sometimes prime numbers are helpful in 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. This is often faster.
A program. 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

Modulo: This operation returns 0 if a number is evenly divisible. We thus can use it to detect a possible prime factor.

Modulo
Java program that detects prime numbers 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); } } } } Output 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
In main, we test some ranges of numbers for primes. As expected, the method allows 2 as a prime, but no other even numbers. And the first primes, 2, 3, 5, 7, are well-known.
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

IsPrime: This is the same method as described in the previous example. It returns a boolean value.

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

Main: Here we invoke isPrimeMemoized twice. It internally calls isPrime once: the memoized result is used the second time.

Java program that uses memoization on prime numbers 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); } } Output true Memoized prime result true
Not optimal. The memoization method is not optimal. The isPrime method is one that a reader helped optimize. But even with the loop, it is slower than using an effective cache.
A 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.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Home
Dot Net Perls