Core Java

Java Prime Numbers Example

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.

Download
You can download the full source code of this example here : JavaPrimeNumbers.zip

Nikos Maravitsas

Nikos has graduated from the Department of Informatics and Telecommunications of The National and Kapodistrian University of Athens. During his studies he discovered his interests about software development and he has successfully completed numerous assignments in a variety of fields. Currently, his main interests are system’s security, parallel systems, artificial intelligence, operating systems, system programming, telecommunications, web applications, human – machine interaction and mobile development.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button