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

Leave a Reply

avatar
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!

Hendra Wijaya Djiono
Guest
Hendra Wijaya Djiono

yea, need to add if (n==2) return true;
at the first line

Javier Villarreal
Guest
Javier Villarreal

“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”

His example program doesn’t do this, but the writer still mentions this. I assume theres code higher up that we cant see checking for 2.

Master Yoda
Guest
Master Yoda

why did you initialize i as 2. int i = 2; What is the 2 number represent ?

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

CompSciStudent
Guest
CompSciStudent

2 is the first prime number

Unknown
Guest
Unknown

How to check if a number is prime or not with using flag.. Basic if else statement!?

unknown
Guest
unknown

There is an error in your code. it’s “if(isPrime[i])” and not “if(primes[i])” (see first for loop)

Joje
Guest
Joje

Your second solution, the one that checks only the odds, tells me that 33 is a prime.. Not really working that well

Javier Villarreal
Guest
Javier Villarreal

Then you are doing it wrong because mine says false

Juan Manuel Furattini
Guest
Juan Manuel Furattini

Your solution could be O(n), so I have a better solution:

public static boolean isPrime(int i) {
if (i == 0 || i == 1) {
return false;
}
for (int prime : new int[] { 2, 3, 5, 7 }) {
if (i % prime == 0 && i != prime) {
return false;
}
}
return true;
}

I use the prime numbers lower than 10 and try to divide the input number by all of them, this method has a O max of O(4)

Tulakr
Guest
Tulakr

What about 11*11 = 121 -> is divisible by 11 and is not prime number. But is not divisible by 2,3,5,7 … your program would fail.

jeff
Guest
jeff

definitely fails.

CoderJohn
Guest
CoderJohn
A good article. Thanks for writing it. I have 2 minor quibbles. 1) Under the repetitions section, in 2 lists, you forgot to cross off 4 (the first multiple of 2). 2) When you’re crossing off, you only need to start at the square of the new prime. e.g. if your new prime is 5, then you don’t need to cross off 5*2, 5*3 or 5*4, because they were already done when the working primes were 2 and 3. The first number you’ll need to cross off is 5*5. Unfortunately, after the square, there is not nearly so convenient a… Read more »
Doc Greystone
Guest
Doc Greystone

Its not very clever to check all numbers till “n” since most of these checkings are unnecessary.

The program gets *a lot* faster if you check the numbers only till the square root of “n”.

Steven Smith
Guest
Steven Smith
I think it would be better to assign another variable to serve as the limit. For example you could do this int sqrtn=(int)Math.sqrt(n); for(int i=3;i<=sqrtn;i+=2){ //body of loop goes here } That would prevent repetitive multiplication or square root checking every time the loop finishes, and it can instead just compare the 2 numbers. Some people might be concerned this will not work when Math.sqrt(n) is a floating point number instead of an integer, but it will work for the same reason that the square root is helpful in the first place. If you increase that number by just 1,… Read more »
Doc Greystone
Guest
Doc Greystone

nice

ambel
Guest
ambel

This is really misleading! test your code..

Brian M Dean
Guest
Brian M Dean
Another way to improve the efficiency of this algorithm is to not bother checking numbers that are divisible by 2 or 3 (instead of just 2). This can be simply done by checking (n % 3) and if it’s 1, add 4 to n, else add 2 to n. That way, n will never be divisible by 2 or 3. The expense of the % operator can even be mitigated by storing it in a variable, i.e. int mod3n . Then when you loop, you simply assign mod3n instead of calculating (n % 3) each time. The algorithm would then… Read more »
Guest
Guest
Guest

Hate to be that “bad guy”, but you’re alg. is broken: if 2 is a prime, then your alg.s above never account for that, i.e. ” if (n%2 == 0) return false ” – that evaluates to true on 2. Also, how does your algorithm take into account number like 25, 35, 45, etc.? All are not divisible by 2.

Guest
Guest
Guest

Never mind Just saw the +=2.

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

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!

Max Kalininskij
Guest
Max Kalininskij
Actually it’s a little more complicated than that, given that you’re incrementing by 2 with each iteration, not by 1 if you remember. You also forgot to replace the “i*i<=n" with "i2<=n" – which was supposed to be the whole bloody point of your suggestion! ;) So anyway, the resulting loop would actually be the following: for (int i = 3, i2 = 9; i2 <= n; i2 += ((2 * i) + 1) + (2 * (i + 1)) + 1, i += 2) Which has the possibility to confuse some people and given that this 2 * i… Read more »
qwerty
Guest
qwerty

Wouldn’t it be i2+=(2*(i+1)+2*(i+1)) instead of i2+=((2*i)+1)+(2*(i+1))+1?
And if we are being efficient, why not use i2+=4*(i+1)?

Its obvious that using the extra variable, i2, will require more calculations than just using i*i, but the over all O() will be the same in both situations, meaning that for much larger values of n, the total runtime will not significantly change.

for(int i=3,i2=9;i2<=n;i2+=4*(i+1),i+=2) and for(int i=3;i*i<=n;i+=2),
both have O(sqrt(n)) running times, assuming that n is prime.

Max Kalininskij
Guest
Max Kalininskij
All these formulas are equivalent. The reason my one appears more confusing and inelegant next to yours, is because of the way I derived it; basically doing the 2*i+1 operation two times in a row, with the second time on i + 1 rather than i. In retrospect I should have given more thought to simplifying the formula before posting it. However now that I can see your solution – it becomes apparent that the i2 variable always increments by a predictable factor of 4 at each iteration. Given this knowledge, it’s possible to skip multiplication altogether with the help… Read more »
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!

Alchemist
Guest
Alchemist

@Andy why dont you start blogging and save the world from all the non-sense!

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

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 »
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.

Thomas Eaves
Guest
Thomas Eaves

Also, the second approach never returns “is prime” because it never checks to see whether the divisor is the candidate for primality.

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.

dhanush
Guest
dhanush

what is “boolean isprime” ?

kos
Guest
kos

no idea.
boolean isPrime() is a method you write in Java or another programming language. it produces a boolean value (true or false) which you can use in other logic.

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

kos
Guest
kos

please rephrase your question, and give an example what you wish to have as result. The number of primes is not finite.

sivasurya
Guest
sivasurya

i need to print all the prime numbers from 0 to maximum integer value in java.. the value of max integer is 2,147,483,647..

kos
Guest
kos
Now I understand! There is a fundamental time/memory trade-off principle in computer science and you want to put everything into memory. There is no reason for this, because you only are interested in the end result: a big list. My approach would be: write to disk, one at at time, then after a good night’s sleep when the program is done, (meaning: all file writes had been successful AND the program is finished), read the contents from disk and do as you like, print them on your t-shirt or whatever. Make sure you have 20GB free disk space for the… Read more »
kos
Guest
kos
The process of deciding if a number is prime is “np-hard” in jargon, because dertermining the prime factors of a number is (if it were not, cryptography would not exist). Meaning there are no methods smarter than the stupid naieve approach. Assuming you are good with computers, then you can cheat like this: a) you can find 1+MAXINT/2 separate computers (MAXINT/2 zombies and 1 master) b) each zombie can communicate in light speed with the 1 master computer. The master counts 3 to MAXINT (+2 every time) and activates a zombie computer (for every number being a possible prime). Every… Read more »
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………

kos
Guest
kos

running isPrime(65) returns true.

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

a997154@rmqkr.net
Guest
a997154@rmqkr.net

DUSNT WORK, 0/10 WOULDNT TRUST AGAIN…

ALSO; KFC IS HIRING

kosterix
Guest
kosterix

No it doesn’t. But the reason is that the html functionality sucks when copy pasting.

kosterix
Guest
kosterix

for (int i=from;ifrom are prime
}
became
for (int i=from;ifrom are prime
}
probably because of the “>” in the comment. Which proves the site itself is not capable of handling code.

kosterix
Guest
kosterix

for (int i=from;i” in the comment. Which proves the site itself is not capable of handling code.

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.

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

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.

trent
Guest
trent

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

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< =sqrt; i+=6) { if(n%(i-1)==0) return false; if(n%(i+1)==0) return false; } return true; }
mommi84
Guest
mommi84

This will fail at least with all numbers lying between two primes, because n^2 > (n-1)(n+1) = n^2-1 always holds.
E.g.: n=35 (5*7), n=143 (11*13), n=899 (29*31) return true.