/** * A Simple Prime Number Program In Java based on definition. */ public class PrimeNumberProgramInJava { public static boolean isPrime(int n) { // prime must be greater than 1 if (n <= 1) { return false; } int numberOfDivisor = 0; for (int i = 1; i <= n; i++) { if (n % i == 0) { numberOfDivisor++; } } // Divisor is only 1 and itself. return numberOfDivisor == 2; } public static void main(String[] args) { for (int n = 2; n <= 100; n++) { if (isPrime(n)) { System.out.print(n + " "); } } } }As shown in the code, all divisors are tested. If divisors are only 2 (1 and the number itself), then it must be a prime. Below is the output of the code:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97The code test all numbers between 2 and 100 and display those that are prime.
We can perform some simple optimization to the program shown in the example above. We know that we don't need to test if a number is divisible by one, because all numbers are. So we can start testing from the number 2.
We can also say that we only need to check for divisors upto the square root of n. Here is a simple explanation
Below is a sample Java Program for Prime Number optimisation discussed above.
/** * A Simple Prime Number Program In Java With Simple Optimisation. */ public class PrimeNumberProgramInJava { public static boolean isPrime(int n) { // prime must be greater than 1 if (n <= 1) { return false; } if (n <= 2) { return true; } for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { for (int n = 2; n <= 100; n++) { if (isPrime(n)) { System.out.print(n + " "); } } } }
The output is still the same:
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
import java.util.Arrays; /** * A Simple Prime Number Program In Java Using Sieve of Eratosthenes. */ public class PrimeNumberProgramInJava { private static void sieveOfEratosthenes(int n) { boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, true); for (int i = 2; i <= Math.sqrt(n); i++) { for (int j = i * 2; j <= n; j += i) { isPrime[j - 1] = false; } } for (int i = 2; i <= n; i++) { if (isPrime[i - 1]) { System.out.print(i + " "); } } } public static void main(String[] args) { sieveOfEratosthenes(100); } }
If you are interested with execution time, here is a code that checks prime numbers between 2 and 10,000. And we run it 10,000 times to have a large execution time.
/** * A Simple Prime Number Program In Java based on definition. */ public class PrimeNumberProgramInJava { public static boolean isPrime(int n) { // prime must be greater than 1 if (n <= 1) { return false; } int numberOfDivisor = 0; for (int i = 1; i <= n; i++) { if (n % i == 0) { numberOfDivisor++; } } // Divisor is only 1 and itself. return numberOfDivisor == 2; } public static void main(String[] args) { long before = System.currentTimeMillis(); for (int i = 0; i <= 10000; i++) { for (int n = 2; n <= 10000; n++) { if (isPrime(n)) { // skip printing // System.out.print(n + " "); } } } long after = System.currentTimeMillis(); System.out.println("Elapsed: " + (after - before) + " millis"); } }On my laptop machine running 3rd generation Core i7 Processor with 8GB RAM, the execution time is below.
Elapsed: 172985 millis
Which is around 3 minutes
If we do the simple optimisation:
/** * A Simple Prime Number Program In Java With Simple Optimisation. */ public class PrimeNumberProgramInJava { public static boolean isPrime(int n) { // prime must be greater than 1 if (n <= 1) { return false; } if (n <= 2) { return true; } for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { long before = System.currentTimeMillis(); for (int i = 0; i <= 10000; i++) { for (int n = 2; n <= 10000; n++) { if (isPrime(n)) { // skip printing // System.out.print(n + " "); } } } long after = System.currentTimeMillis(); System.out.println("Elapsed: " + (after - before) + " millis"); } }
We could see drastic improvement. The execution is down to 5 seconds from 3 minutes.
Elapsed: 4879 millis
Using Sieve of Eratosthenes will give even more dramatic improvements:
import java.util.Arrays; /** * A Simple Prime Number Program In Java Using Sieve of Eratosthenes. */ public class PrimeNumberProgramInJava { private static void sieveOfEratosthenes(int n) { boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, true); for (int i = 2; i <= Math.sqrt(n); i++) { for (int j = i * 2; j <= n; j += i) { isPrime[j - 1] = false; } } for (int i = 2; i <= n; i++) { if (isPrime[i - 1]) { // Skip printing // System.out.print(i + " "); } } } public static void main(String[] args) { long before = System.currentTimeMillis(); for (int i = 0; i <= 10000; i++) { sieveOfEratosthenes(10000); } long after = System.currentTimeMillis(); System.out.println("Elapsed: " + (after - before) + " millis"); } }
It is now down to 440 milliseconds. Which is around 400 times faster than the original code!
Elapsed: 440 millis