Java Prime Number Method

Test for prime numbers using a for-loop and if-statements. Introduce 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

Main: We test some ranges of numbers for primes. We print the first primes—the primes 2, 3, 5, 7, are well-known.

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

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java Prime Number Method

Related Links:

.Net

Java

Related Links