Prime Number MethodTest for prime numbers using a for-loop and if-statements. Introduce an isPrime method.
Java
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
Detail This operation returns 0 if a number is evenly divisible. We thus can use it to detect a possible prime factor.
Modulo
Detail 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
Detail This is the same method as described in the previous example. It returns a boolean value.
Detail This is a wrapper for isPrime. It uses a HashMap to see if a number's status has already been recorded.
Detail Here 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
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.
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.