Home
Map
Prime Number MethodTest for prime numbers using a for-loop and if-statements. Introduce an isPrime method.
Java
This page was last reviewed on Jan 20, 2024.
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.
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).
Home
Changes
© 2007-2024 Sam Allen.