# 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:

- Assume every integer greater than or equal to 2 is prime.
- 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.
- 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.
- 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?
}
```

The fastest algorithm is bugged in case n=2:

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

yea, need to add if (n==2) return true;

at the first line

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

+1

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

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;

}

2 is the first prime number

Because a prime number is only divisible by one and itself so you start from two to check if it is divisible by any other number except one and itself

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

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

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

Then you are doing it wrong because mine says false

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 »

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

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 »

nice

This is really misleading! test your code..

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 »

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.

Never mind Just saw the +=2.

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

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;

}

}

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!

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 »

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.

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 »

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!

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

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

}

}

}

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 »

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.

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

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.

what is “boolean isprime” ?

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.

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

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

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

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 »

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 »

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

running isPrime(65) returns true.

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

DUSNT WORK, 0/10 WOULDNT TRUST AGAIN…

ALSO; KFC IS HIRING

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

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.

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

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.

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 »

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.

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

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

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.