In this example we are going to talk about prime numbers. Prime numbers are one of the most important subsets of physical numbers. A positive integer p > 1 is a prime if and only if its positive divisors are only itself and 1. For example, 5,13,17,19,23 and so on. It is interesting that Euclid proved that there is no largest prime number. Even more interestingly there is no known formula that can compute all prime numbers, and as you can imagine this is one of the hottest problems of mathematics. 2^(57,885,161) − 1 is the biggest known prime number, until now.
Prime numbers are such an important aspect of mathematics that several prizes are being awarded for researchers that achieve several academic and engineering milestones on the subject. This is because Prime numbers have such a rich amount of valuable properties that are suitable or necessary for major theoretical and practical applications. For example Cryptography is basically founded upon prime numbers. Most of our communications that take place every day along the Internet, rely on the existing abilities to generate and manipulate prime numbers.
In this tutorial we will create a Java program that takes a positive integer n as input and prints out all the prime numbers such that :
p : 1 < p < n.
1. A simple implementation
Here is the most simple and least efficient approach possible.
JavaPrimeNumbers.java:
package com.javacodegeeks.core.primenumbers;
public class JavaPrimeNumbers {
public static void main(String[] args){
for(int i = 2 ; i < 70; i++)
if(JavaPrimeNumbers.primeTest(i))
System.out.println(i);
}
public static boolean primeTest(long n){
for(long i = 2 ; i < n ; i++)
if(n%i == 0)
return false;
return true;
}
}
For every number n until 70, we check if there exists a number k : 2 < i < n that divides n. As you can see this algorithm is O(N^2), which is really bad. One quick improvement would be not to check all the numbers until n but until sqrt(n). So we can now loop through k : 2 < i < sqrt(n) -> If there exists a number i > sqrt(n) that divides n, then there also exists a number i < sqrt(n) that also divides n. So it suffices to check until sqrt(n).
JavaPrimeNumbers.java:
package com.javacodegeeks.core.primenumbers;
public class JavaPrimeNumbers {
public static void main(String[] args){
for(int i = 2 ; i < 70; i++)
if(JavaPrimeNumbers.primeTest(i))
System.out.println(i);
}
public static boolean primeTest(long n){
for(long i = 2 ; i < Math.sqrt(n) ; i++)
if(n%i == 0)
return false;
return true;
}
}
2. Eratosthenes's Seive
Of course the exists a plethora of much more efficient algorithms that do the job. The most famous of which is the Eratosthenes's Seive
JavaPrimeNumbers.java:
package com.javacodegeeks.core.primenumbers;
public class JavaPrimeNumbers {
public static void main(String[] args){
int N = 100;
boolean[] isPrime = new boolean[N + 1];
JavaPrimeNumbers.initializeSeive(isPrime);
for(int i = 2 ; i < N; i++)
if(isPrime[i])
System.out.println(i);
}
public static void initializeSeive(boolean[] seive){
int N = seive.length;
System.out.println(N);
for (int i = 2; i < N; i++) {
seive[i] = true;
}
for (int i = 2; i*i <= N; i++) {
if (seive[i]) {
for (int j = i; i*j <= N; j++) {
seive[i*j] = false;
}
}
}
}
}
This algorithm removes from the sieve all the composite numbers and leaves out the primes. For example it removes all the multiples of 2, all the multiples of 3, all the multiples of 4 e.t.c. That's the logic of it.
Download the Source Code
This was an example on Prime Numbers.
You can download the full source code of this example here : JavaPrimeNumbers.zip
