Main Tutorials

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 Author

Comments

Subscribe
Notify of
89 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Albi Ho
8 years ago

The fastest algorithm is bugged in case n=2:

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

Javier Villarreal
6 years ago
Reply to  Albi Ho

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

martin
5 years ago

+1

Hendra Wijaya Djiono
8 years ago
Reply to  Albi Ho

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

Tatiana
4 years ago

The second solution “boolean isPrime(int n)” isn’t correct. It returns true with 4.

CoderJohn
7 years ago

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 pattern for crossing off.

keshav
11 years ago

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

Deepak
2 years ago
Reply to  keshav

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

}

howto execute this program ?

Deepak
2 years ago
Reply to  keshav

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?

}
shubham manjhi
1 year ago

boolean flag = true;
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0) {
flag = false;
break;
}
}
if (flag == true) {
System.out.println("it is a prime");
} else {
System.out.println("it is not prime");
}

Bryan Karlan
1 year ago

Please help me understand why we should care about Prime Numbers. This seems to be a mathematical oddity that has no practical usage in any circumstance other than to teach how to code. Since Prime numbers are so unusable I fail to see why I should care to understand how to make searching for a Prime Number and Prime Factors more efficient. Now if this were about some financial calculation such as calculating NOI more efficiently, then that would make sense to me. But I don’t understand Prime Numbers, I don’t care to understand Prime Numbers and I fail to see why Prime Numbers matter in this or in Tim Bulchaka’s class in which they repeatedly use the Prime Number calculation. Under what circumstance, in the real world, would I care to figure out the highest prime factor? Because of it’s lack of real world usage, I refuse to waste brain space trying to understand what this is or how to calculate it. Please tell me if I’m wrong.

Sandeep Kumar
2 years ago

If we follow this method for first 10,000 numbers, then we have to run the loop by 11,958 times
instead of Arrays.fill you can use the below loop then we can reduce the loop iterations to 787 times only.

This code will almost reduce the iterations to less than half.

Note : Please check the java source code implement of Arrays.fill

public static void fillSieve() {

		//Arrays.fill(primes, true); // assume all integers are prime.



          int totalIterations = 0;
          // this for loop does the same job as Arrays.fill

      		for (int i = 0; i < primes.length; i++) {
      
      			if (i % 2 == 0)
      
      				primes[i] = false;
      
      			else if (i % 3 == 0) {
      
      				primes[i] = false;
      
      			} else if (i % 5 == 0 || i % 7 == 0) {
      
      				primes[i] = false;
  
  			} else {

				primes[i] = true;

			}

		}

		primes[0] = primes[1] = false; // we know 0 and 1 are not prime.

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

			// totalIterations++;

			// 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 <= 1000; j++) {

					totalIterations++;

					primes[i * j] = false;

				}

			}

		}

System.out.println( "totalIterations "+totalIterations);

	}
Dan
4 years ago

In the 2nd solution, I can’t figure out why multiply 2 in the for expression…

alter
3 years ago
Reply to  Dan

The highest possible divider of N is always N / 2. There is simply no point in checking it further since for I > N / 2 result of N / I would always be 0 < result < 2

swathi
4 years ago

why we use boolean

swathi
4 years ago

why we use boolean key word

Thelast
2 years ago
Reply to  swathi

Because we want to get true false value for the prime number Or not

Fuck Oscar Sanchez
5 years ago

This was shit. Delete this fucking article.

Greg
5 years ago

What is teh time comlpexity of this?

amudary
5 years ago

first algorithm is fine with 2 since it won’t enter to for loop it will return true… the only problem is when num < 2…

Master Yoda
6 years ago

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

Arinze
5 years ago
Reply to  Master Yoda

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

CompSciStudent
6 years ago
Reply to  Master Yoda

2 is the first prime number

Unknown
6 years ago

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

unknown
6 years ago

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

Joje
6 years ago

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

Javier Villarreal
6 years ago
Reply to  Joje

Then you are doing it wrong because mine says false

Doc Greystone
7 years ago

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
7 years ago
Reply to  Doc Greystone

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, you will get a number that is above the square root, even if the square root is a floating point number. Every factor above the square root would be associated with a factor below the square root, so if you check a number above the square root, you are wasting your time.

Doc Greystone
7 years ago
Reply to  Steven Smith

nice

Brian M Dean
8 years ago

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 be something like:

(Sorry but for some reason I can’t type proper java code in this comment, so the below will have to do)

int n = someinitialvalue;
int mod3n = (n % 3);
(then inside the loop do)
if (mod3n == 2) {
n += 2;
mod3n = 1;
} else {
n += 4;
mod3n = 2;
}

That way, if n is assigned some value not divisible by 2 or 3, then each subsequent n will also not be divisible by 2 or 3

Then if we are testing if p is prime, obviously we would want to test (p % n) in the loop and return false if it’s 0.

Guest
8 years ago

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
8 years ago
Reply to  Guest

Never mind Just saw the +=2.

juanmf
8 years ago

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
9 years ago

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
9 years ago

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
9 years ago
Reply to  Frd

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 + 1 operation has to be basically performed twice in a row, I wonder if it wouldn't be faster to just square it instead after all.
I might run a few tests.

And no shame in gaining a few milliseconds. I would ordinarily regard such micro-optimizations as superfluous, in line with the conventional wisdom on such matters – but when it comes to something as hideously computationally expensive as determining the primality of large numbers – we need every iota of performance we can squeeze out!
Especially if you need to figure out a whole load of numbers like I'm trying to do.

qwerty
9 years ago

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
9 years ago
Reply to  qwerty

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 of yet another loop variable, although without inside knowledge of the compiler’s magic it’s hard to tell if this would make things more efficient:

for (int i = 3, i2 = 9, i3 = 16; i2 <= n; i += 2, i2 += i3, i3 += 8)

As for runtimes, yes you are correct, but nontheless for large values of n, that's a large amount of calculations. It can't hurt to figure out the optimal calculation. Imagine if such a method will be used in a multi-threaded environment and called a few times every second. Always optimize when it comes to utility functions like this.

Andy
9 years ago

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
7 years ago
Reply to  Andy

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

Alex
9 years ago

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
9 years ago

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 the first ” + end_value + ” numbers”);
}

kaushik Lele
9 years ago

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
8 years ago
Reply to  kaushik Lele

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

Franco
10 years ago

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
10 years ago

what is “boolean isprime” ?

kos
10 years ago
Reply to  dhanush

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
10 years ago

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
10 years ago
Reply to  sivasurya

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

sivasurya
10 years ago
Reply to  kos

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
10 years ago
Reply to  sivasurya

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

So the key to success is IMHO keep the program stupid and let it calculate every number from scratch. Do not use any sieve method.

Since you only would have the program do the job once, the total time between start of programming and end result would be minimal.

If you have more time to kill OR suspect power outages, let the program run on your office pc. If you have no office pc, you can write some code to backup after every 1000 writes to another file on another disk drive. When the program starts, check the most recent file in the write folder, if it is corrupt check the backup drive, and start from that point on again. If you export the program to a jar and put it in your startup folder, when your pc reboots it will pick up from where it started. Something like that.

Does that help?

kos
10 years ago
Reply to  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 time a number was found to be prime the master saves it to disk.

The zombie has the following tasks:
1) become active (get a number)
2) add very fast all multiples of that number and store (except the number gotten), until MAXINT reached. Computers can do that.
If MAXINT reached, report READY to the master.
3) report the lowest (initially the original number*2) number on their list. Can be done in parallel with task 2.
4) remove the lowest number. If no number available, report DONE and shutdown the zombie.

Now every time the master takes a new number, its zombies hear it and if it is not a prime,
one zombie reports not a prime, and all zombies remove any numbers on their list = 1 zombie (3,6,9,..); number=5-> 1 extra zombie (storing 5,10,15 …) etc.

Observe the following:
1) the first zombies will do the most work, because the most often their numbers will have to be added in the first place and removed once the master prime moved on.
2) every action is “constant time”, and very little time. say the master is currently at number 293875397, which could be a prime or not, it will have 293 million zombie computers at its disposal and they all can return in an instant if that number is on their list (or not, in which case the master moves on). Of course, there is cost in the activation cost of that many zombies, but that is only one per prime.

If you were willing to do this, you would have more fun applying the above approach to crack the codes of the NSA or CIA.