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

## Leave a Reply

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)

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

nice

my implementation:

void printPrimes(int max) {

boolean isPrime = true ;

for(int i=1 ; i<= max ; i++ ) {

for(int j= 2 ; j<= i; j++) {

if(i%j == 0) {

isPrime = false ;

break;

} //end if

} //end for

if(isPrime) System.out.print(i + " ; " );

isPrime = true ;

} //end outer for

System.out.println();

}

This is really misleading! test your code..

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

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.

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!

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.

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

}

}

}

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

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

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

DUSNT WORK, 0/10 WOULDNT TRUST AGAIN…

ALSO; KFC IS HIRING

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.

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

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.

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.

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.

Fails on -1.

Fails on 1000*1000*1000.

Performance also horrible.

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

Hi datruchosen,

Current comment does not support posting source code correctly, i’m still working on it. At the moment i modified your code, please review. And really appreciated sharing your isPrime() method.