Prime Number Program in Java
Prime Number is a concept in math, specifically in number theory. A Prime Number is a whole number greater than 1 that has no positive divisors except 1 and itself. For example, the number 7 is prime because it has no other divisor except 1 and 7. While 6 is not a prime number because 2 and 3 can divide it. If you need to write a program that needs to check if a number if prime or not, below are some examples for Prime Number Program in Java.Simple Prime Number Program in Java
Since by definition, a prime number is a whole number greater than 1 with no other divisor except one and itself, we can use this as literal guide for the algorithm. Below is a simple Prime Number Program in Java that uses this definition in it's logic:
/**
* 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.
Prime Number Program in Java With Simple Optimization
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
- Say n has a divisor k where k > square root of n.
- Then there is a number p where n = k p
- If p > square root of n, then k p > n
- Therefore, p < square root of n
- But we have checked all numbers less than or equal to square root of n. Hence, there is no need to check for divisors > square root of n
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
Prime Number Program In Java Using Sieve of Eratosthenes
If we want to display all prime numbers between 1 and n, then the Sieve of Eratosthenes would be very useful. The logic is to have an array of boolean from 1 to n and initialze each with true. Which means we assume all are prime numbers. Then we check all numbers between 2 and square root of n, and mark all numbers it can divide with false (except itself). Then we will see all those left must be really primes! Below is a sample program to illustrate the Sieve of Eratosthenes.
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);
}
}
Execution time
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