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;
}

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:


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?
}

About the Author

author image
Oscar_Sanchez

Comments

avatar
48 Comment threads
34 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
62 Comment authors
DanswathiTatianaFuck Oscar SanchezGreg Recent comment authors
newest oldest most voted
Albi Ho
Guest
Albi Ho

The fastest algorithm is bugged in case n=2:

if (n%2==0) return false; // will return FALSE! But 2 is PRIME!

keshav
Guest
keshav

Its a nice solution using the divisibility test but I found something equally interesting using nothing but Math class rounding properties
http://www.youtube.com/watch?v=vbU-msSq93M

Jose Luis Montes de Oca
Guest
Jose Luis Montes de Oca

Second solutions fails by including 4 as a prime.
Third solution fails by excluding 2 as a prime.

John
Guest
John

True, the second solution is missing an “=” and I guess it was typeformatted wrong with the html tags.

And yeah, the second solution forgot whether n==2.

The prime sieve is pretty cool, though. Good job overall, just a couple of typos.

BlogReader
Guest
BlogReader

Or use BigInteger.isPrime()

Thug
Guest
Thug

Isn’t it better to use addition instead of multiplication in the inner for statement?

for (int j=2*i;j<primes.length;j+=i) {
primes[j]=false;
}

I'd like to know how to list prime numbers greater than Integer.MAX_VALUE.

Mexflubber
Guest
Mexflubber

Actually it can be optimized by stoping at your current number squared root, as that’s the highest divisible number that number will have. Also you could create your own class and make it Enumerable, so you can use a yield return without having to calculate all of them before you need them.

Alex Sales
Guest
Alex Sales

only solution 1 is correct ~_~

datruchosen
Guest
datruchosen

/************************************************************************** * This java method, isPrime( z ), takes an integer input, z, and * * determines its primality. If z is prime, isPrime( z ) returns * * true; otherwise it returns false. In the case that an integer value * * z < 1 is entered, isPrime( z ) will throw an exception, as an integer * * z is prime if, and ONLY if, for z = x * y, x = 1, or y = 1. * **************************************************************************/ public static boolean isPrime( int primer ) throws PrimeNumberException { int i = 0; int j = 0;… Read more »

datruchosen
Guest
datruchosen

by the way, where you see “1*/” in my previous post in the first branch statement, should really be less than 1 symbolically … don’t know what’s up with that

datruchosen
Guest
datruchosen

The code I posted last week had a minor error; here is the correct code (I still haven’t been able to implement a more efficient method of determining primality, however). public static boolean isPrime( int primer ) throws PrimeNumberException { int i, j, k = 0; if( primer 2 && primer%2 == 0 ) return false; else { for( i = 3; i < primer; i += 2 ) { for( j = i; j < primer; j += 2 ) { k = i * j; /*I incorrectly wrote this outside the loops */ if( k == primer )… Read more »

ashish
Guest
ashish
private void generatePrimeLessThan(int x){
int number[] = new int[x];
int i=0;
int j=0;
boolean isPrime = false;
for(i=0;i&lt;x;i++){
number[0]=0;
}
number[2]=1;
for(i=3;i=2){
if(i%j==0){
isPrime=false;
break;
}
j–;
}
if(isPrime){
number[i]=1;
}
}
for(i=0;i&lt;number.length;i++){
if(number[i]==1){
System.out.print(i+&quot; &quot;);
}
}
}
private void generatePrimeNumberSeq(int x){
int number[]=new int[x];
int i=3,j=0;
int count=1;
number[0]=2;
boolean isPrime=true;
while(count=2){
if(i%j==0){
isPrime=false;
break;
}
j–;
}
if(isPrime){
number[count]=i;
count++;
}
i++;
}
for(i=0;i&lt;number.length;i++){
System.out.print(number[i]+&quot; &quot;);
}
}
shiv
Guest
shiv

/** * Test for prime numbers * @param n * @return */ public static boolean isPrime(int n) { if(n < 4) return true; //test for all multiples of 2 if ((n & 1) == 0) return false; //test for all multiples of 3 if ((n%3) == 0) return false; //other wise test all odd numbers, but we are checking only for probable prime numbers of the // form 6K+1/6K-1 k>1; int sqrt = (int) Math.sqrt(n); for(int i=6; i

trent
Guest
trent

Great Post! this helped me a lot with an app im working on.

Kosterix
Guest
Kosterix

Guys what are you trying to do here? Trying to learn Java, or trying to program algorithms?
Incredible how sloppy you are, and you are trying to re-invent the wheel, and badly at that:
Vaengai WTF is for(i=3;i=2)
Datruchosen WTF is a PrimeNumberException?

Simply use a singleton for creating a cache once.

kosterix
Guest
kosterix

Below you will find a tested working class. It uses caching to speed up recalculating + will resize the cache when needed. Its main method contains some sample tests. Enjoy! package kos.lib.math; import java.util.Arrays; import java.util.Vector; /** * CachedPrimes is used primarily to get the next prime bigger than a given number, * fast. * * By its nature it is a singleton (load once, use forever). * Example usage: * CachedPrimes.main( number-to-test cache) : test if 1511 is a prime and also set up a cache. * new CachedPrimes(x).isPrime(x) : for a x decide if it is prime. *… Read more »

kosterix
Guest
kosterix

Is it not more interesting how much time it will take to factor a really big number into two or more primes (and how many pairs as a side). If the original is a prime, any algorithm will take the most time, of course. How this can be used for encrypting I never understood.

a997154@rmqkr.net
Guest
a997154@rmqkr.net

DUSNT WORK, 0/10 WOULDNT TRUST AGAIN…

ALSO; KFC IS HIRING

Sthita
Guest
Sthita

//simple one… ur code is little complex for a given no to know is prime or not public static boolean isPrime(int number){ for(int i=2; i<number; i++){ if(number%i == 0){ return false; //number is divisible so its not prime } } return true; //number is prime now }

sangramkeshari.panda
Guest
sangramkeshari.panda

//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;
}

It seems wrong…………………………………..

check in 13195 o/p is 3,7,35,65,91…
but 35 and 65 r not prime………

sivasurya
Guest
sivasurya

hey there.. am trying to find out the prime numbers from 0 to maximum integer value.. but, neither the boolean array, nor the long array, nor the integer array allows me to store such a huge value.. is there any other option…??

dhanush
Guest
dhanush

what is “boolean isprime” ?

Franco
Guest
Franco

I did something similar. Basically I would only take 1/3 of the number being passed through our ‘isPrime’ function and loop through values in that array of numbers. I liked your way better, definitely more efficient than looping from 2 -> n value.

kaushik Lele
Guest
kaushik Lele

In second approach

boolean isPrime(int n) {
for(int i=2;2*i<n;i++) {

}}

It fails for n=4
loop should start from i=1

It may fail for many other numbers as we are skipping division by 2.

Piergiorgio Calzi
Guest
Piergiorgio Calzi

I may be completely wrong and my code could be completely unefficient, but it shows all the primes numbers in the first n (end_value) integers. Slightly different intent, but from here you can extract the test. public static void whileStatement (String[] args) { int loop_value1 = 1; int loop_value2 = 1; int end_value = 3000; int number_of_primes = 0; while (loop_value1 <= end_value) { while (loop_value2 (loop_value1 /2)) { System.out.println(loop_value1 +” is a prime”); number_of_primes++; break; } else if (loop_value1 % loop_value2 == 0) { break; } loop_value2++; } loop_value1++; loop_value2 = 2; } System.out.println(number_of_primes + ” primes discovered in… Read more »

Alex
Guest
Alex

i tried like this. but it didn’t work. Somebody knows why?

ArrayList primeNumbers = new ArrayList();
for (int i = 0; i < numbersToCheck.length; i++) {
for (int div = 1; div < numbersToCheck[i]; div++) {
if (numbersToCheck[i]%div == 0 && div != numbersToCheck[i])
{}
else
{
primeNumbers.add(numbersToCheck[i]);
}
}
}

Andy
Guest
Andy

Did you actually test your code? Obviously not, since your first solution will treat 2 as non-prime and 1 as prime! What non-sense!

Frd
Guest
Frd

A simple way to avoid computing i*i in the loop is to put that square value into a variable i2 that is also incremented.
As (i+1)*(i+1)-i*i = 2*i+1, one can change for(int i=3;i*i<=n;i+=2) into for(int i=3,i2=9;i*i<=n;i2+=2*i+1,i+=2). Eh hop, some few milliseconds gained!

John Hall
Guest
John Hall

So far as I can tell, this does not check is the number if divisible by primes. try something like this. I set it up for a prime generator.

boolean isPrime = true;
for(int n=2; n<=ui; n++){
isPrime = true;
for(int o=2; o<n; o++)
{
if (n%o==0)
isPrime=false;
}
}

juanmf
Guest
juanmf

If no previous prime divides a num, then that num is a prime. public static int[] primes() { int[] primes = new int[10000000]; primes[0] = 3; primes[1] = 5; primes[2] = 7; int index = 3; for (int n = 11; index = top) { // System.out.println(“j(prime): ” + j + “; i(test): ” + n + “; Top: ” + top); if ((j != 0) && (n % j == 0)) { prime = false; break; } } else { break; } } if (prime) { System.out.println(n); primes[index++] = n; } } return primes; }