How To Determine A Prime Number In Java

http://www.mkyong.com/java/how-to-determine-a-prime-number-in-java/

A very important question in mathematics and security is telling whether a number is prime or not. This is pretty useful when encrypting a password. In this tutorial, you will learn how to find whether a number is prime in simple cases.

Trivial Cases

We learned numbers are prime if the only divisors they have are 1 and itself. Trivially, we can check every integer from 1 to itself (exclusive) and test whether it divides evenly.

For example, one might be tempted to run this algorithm:

//checks whether an int is prime or not.
boolean isPrime(int n) {
    for(int i=2;i<n;i++) {
        if(n%i==0)
            return false;
    }
    return true;
}

This doesn’t seem bad at first, but we can make it faster – much faster. Consider that if 2 divides some integer n, then (n/2) divides n as well. This tells us we don’t have to try out all integers from 2 to n. Now we can modify our algorithm:

//checks whether an int is prime or not.
boolean isPrime(int n) {
    for(int i=2;2*i<n;i++) {
        if(n%i==0)
            return false;
    }
    return true;
}

PS: Prime: 2,3,5,7,11,13,17... the above i can start from 2, because 2,3 is prime. test 4 at the beginning.
With some more efficient coding, we notice that you really only have to go up to the square root of n, because if you list out all of the factors of a number, the square root will always be in the middle (if it happens to not be an integer, we’re still ok, we just might over-approximate, but our code will still work).

Finally, we know 2 is the “oddest” prime – it happens to be the only even prime number. Because of this, we need only check 2 separately, then traverse odd numbers up to the square root of n. In the end, our code will resemble this:

//checks whether an int is prime or not.
boolean isPrime(int n) {
    //check if n is a multiple of 2
    if (n%2==0) return false;
    //if not, then just check the odds
    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return true;
}

As you can see, we’ve gone from checking every integer (up to n to find out that a number is prime) to just checking half of the integers up to the square root (the odd ones, really). This is a huge improvement, especially considering when numbers are large.

Repetitions

Let’s say you write a program where you’re asked to check whether many numbers are prime; not just once. Even though our program above is highly optimized for that algorithm, there exists another way specifically suited for this situation: The Prime Sieve.

Here’s the basic idea:

1. Assume every integer greater than or equal to 2 is prime.
2. Start at the beginning of the list, if the number is prime, cross out every multiple of that number off the list. They are not prime.
3. Go to the next number, if it is crossed out, skip it – it is not prime. If it is not crossed out, it must be prime, cross out it’s multiples.
4. Repeat

Let’s see what this means. Consider the list:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

2 is prime… cross out it’s multiples. Our list now looks like:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …

You can see why 2 is the only prime. By now doing it with 3, we cross out 6 (already crossed out), 9, 12(already crossed out), 15, etc. Eventually, your list will look like this:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …

And our primes are the ones left over: (2,3,5,7,11,13,17,19,23,29,…). In code, you might want to keep track of this list as an array. Meaning you’ll go through n numbers to set up this “sieve”, but you’ll make up for it when repeatedly calling the function, since it will return an instantaneous value whether a number is prime or not. Here’s what it will look like. Of course, you can edit this yourself to suit your needs:

This is AWEEEESOME!!!!!!!
boolean[ ] is AWEEESOM!!!!

import java.util.Arrays;
//global array just to keep track of it in this example, 
//but you can easily do this within another function.
 
// will contain true or false values for the first 10,000 integers
boolean[] primes=new boolean[10000]; 
//set up the primesieve
public void fillSieve() {
    Arrays.fill(primes,true);        // assume all integers are prime.
    primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
    for (int i=2;i<primes.length;i++) {
        //if the number is prime, 
        //then go through all its multiples and make their values false.
        if(primes[i]) {
            for (int j=2;i*j<primes.length;j++) {
                primes[i*j]=false;
            }
        }
    }
}
 
public boolean isPrime(int n) {
    return primes[n]; //simple, huh?
}