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

About the Author

Oscar_Sanchez

Comments

  • dhanush

    what is “boolean isprime” ?

    • 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

    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

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

      • 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

          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

            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.

  • 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

      running isPrime(65) returns true.

  • 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

    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

  • http://[email protected] [email protected]

    DUSNT WORK, 0/10 WOULDNT TRUST AGAIN…

    ALSO; KFC IS HIRING

    • kosterix

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

    • 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

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

  • 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

    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. 
     *  CachedPrimes cp = new CachedPrimes(x);
     *      loop -&amp;gt; cp.isPrime(x) : for a number of x decide very fast if it is prime.
     * @author Kos
     *
     */
    public class CachedPrimes {
     
    	/**
    	 * DEFAULT_CACHE_OF_PRIMES is the minimum amount of cached primes.
    	 * Cache does not shrink below that.
    	 * 
    	 * @version 1.1 2012-10-21 adding resize functionality 
    	 * @version 1.0 2012-08    initial
    	 * @author Kos
    	 */
    	private static final int	DEFAULT_CACHE_OF_PRIMES	= 100;
     
    	/**
    	 * safeguard against blowing up the jvm.
    	 * Even if client creates 1000 CachedPrimes instances, they all re-use the same cache,
    	 * so that part is covered.
    	 */
    	public static final int	MAX_CACHE_OF_PRIMES	= 1000*1000*1000; //a billion should suffice.
     
    	/**
    	 * 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.
    	 * 
    	 * Note kos: this will still take up unnecessary space, that is, 10000x8 bits.
    	 * What you really want is something of 10000/8 bytes. 
    	 */ 
    	static boolean[] primes=new boolean[DEFAULT_CACHE_OF_PRIMES];
    	static boolean initialized = false;
    	static int size = DEFAULT_CACHE_OF_PRIMES; //allow for growing the primes array.
     
    	/*
    	 * sets up the primesieve.
    	 * Keep private, so that the call must be made from the constructor, like
    	 * CachedPrimes().next() or CachedPrimes.next();
    	 */
    	private static void initialize() {
    	    Arrays.fill(primes,true);        // assume all integers are prime.
    	    primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
    	    fillSieve(2);
    		initialized = true;	    
    	   }
     
    	/**
    	 * This method can be used to hack directly into the internal store of cached primes.
    	 * Sieving the part [len .._newsize-1] without sieving [1..len]:
    	 * 
    	 * fillSieve starts with a 'known set'.
    	 * 
    	 * Example usage:
    	 * if from &amp;gt; primes.length, will fill, otherwise exit.
    	 *
    	 * @param from
    	 *
    	 * @version 2012-10-21 1.0 initial
    	 * @author Kos
    	 */
    	public static void fillSieve(int from) {
    		int base = 2; 
     
    		//pre: primes[from..] are all false. Some of primes[2..from] are true.
    		for (int i=from;ifrom are prime
    		}
    		/*
    		 * pre: Some of primes[2..from] are true. primes[from..] are all true. 
    		 * if they are a multiple, make em false.
    		 */
    		for (int i=base;i&amp;lt;primes.length;i++) {
    			/*
    			 * if i is not prime, then primes[i] was already set to false,
    			 * because i is a multiple of a prime p and something, and p was already passed,
    			 * so only if primes[i]==true we need all multiples up to primes.length.
    			 */
    	        if(primes[i]) {
    	            for (int j=base;from&amp;lt;i*j &amp;amp;&amp;amp; i*j&amp;lt;primes.length ; j++) {
    	                primes[i*j]=false;
    	            }
    	        }
    	    }
    	}
     
     
    	public CachedPrimes(){
    		_setup(DEFAULT_CACHE_OF_PRIMES);
    	}
     
     
    	public CachedPrimes(int cache){
    		_setup(cache);
    	}
     
    	/**
    	 * This method is the generic constructor.
    	 * @version 2012-09 1.0 initial
    	 * @author Kos
    	 */
    	private void _setup(int cache) {
    		primes=new boolean[cache];
    		initialize();		
    	}
     
    	/*
    	 * METHODS
    	 */
     
    	/**
    	 * 
    	 * This method grows or shrinks the cache
    	 * 
    	 * @param newsize
    	 *
    	 * @version 1.0 2012-10-21 initial
    	 * @author Kos
    	 */
    	private static void resize(int newsize){
    		//no initialize needed because it is private		
     
    		if(newsize&amp;gt;MAX_CACHE_OF_PRIMES){
    			System.out.println(&quot;newsize &amp;gt; &quot;+MAX_CACHE_OF_PRIMES+&quot; -&amp;gt; newsize &quot;+newsize+&quot; rejected -&amp;gt; CachedPrimes cache size kept at &quot; + DEFAULT_CACHE_OF_PRIMES);
    			newsize = MAX_CACHE_OF_PRIMES;			
    		}
     
    		if(newsize CachedPrimes cache size kept above &quot; + DEFAULT_CACHE_OF_PRIMES);
    			return;
    		}
    		int len = primes.length;
    		int half = len&amp;gt;&amp;gt;1;
    		int db = len&amp;lt; newsize &amp;amp;&amp;amp; newsize &amp;gt; half ){
    			System.out.println(&quot;newsize &quot;+newsize+&quot; rejected (size=&quot;+len+&quot;)-&amp;gt; CachedPrimes shrinks only below &quot; + half);
    			return; //debug because it is a side effect of the caller
    		}
    		//at least double it, or shrink it to below half:
    		int _newsize =  len&amp;lt; newsize &amp;amp;&amp;amp; newsize &amp;lt; db ? db : newsize;
    		boolean[] _primes= Arrays.copyOf(primes,_newsize);
    		//calculate the rest if needed
    		primes = _primes;
    		/*
    		 * until the end.. that is, until [_newsize-1]
    		 */
    		fillSieve(len); 
    	}
     
    	/**
    	 * This method returns (if already computed, else computes) if n is prime.
    	 * 
    	 * Example usage:
    	 * isPrime(11) -&amp;gt; true
    	 * isPrime(12) -&amp;gt; false
    	 * isPrime( 0 ) -&amp;gt; false + warning.
    	 * isPrime(-11) -&amp;gt; false + warning.
    	 * isPrime(1e1111) -&amp;gt; illegal argument (too big).
    	 *
    	 * @param n
    	 * @return
    	 *
    	 * @version 2012- 1.0 initial
    	 * @author Kos
    	 */
    	public static boolean isPrime(int n) {
    		if(nMAX_CACHE_OF_PRIMES){
    			throw new IllegalArgumentException(n+&quot;==n&amp;gt;MAX_CACHE_OF_PRIMES=&quot; + MAX_CACHE_OF_PRIMES+&quot; -&amp;gt; isPrime(n) n too big. Exiting...&quot;);
    		}
     
    		if(n==1) return false;
    		//n&amp;gt;=2:
    		resize(n+1);
    	    return primes[n]; //simple, huh?
    	}
     
    	/**
    	 * 
    	 * This method returns the same number if it is a prime, or else the nearest prime &amp;gt;n.
    	 * 
    	 * Example usage:
    	 * CachedPrimes.next(15) -&amp;gt; 17
    	 *CachedPrimes.next(150000) -&amp;gt; resizes the cache, possibly blowing up the jvm.
    	 * @param n
    	 * @return
    	 *
    	 * @version 1.1 2012-10-24 forgot the _n++ -&amp;gt; loop hang.
    	 * @version 1.0 2012-10 initial
    	 * @author Kos
    	 */
    	public static int next(int n){
    		if (!initialized) initialize();
     
    		int _n=n;
    		while(_n&amp;lt;primes.length){
    			if( isPrime(_n)) return _n;
    			_n++;
    		}
    		System.out.println(&amp;quot;resizing to 2*&amp;quot;+primes.length +&amp;quot; ...&amp;quot;);
    		resize( primes.length &amp;lt;n with +10, else to n+10. Doubling is too expensive. 
    	}
     
    	/**
    	 * This method tests given numbers by setting up a cache.
    	 * If no cache was specified, it is derived from the numbers to test.
    	 * 
    	 * Example usage:
    	 *  main() : test if 1511 is a prime
    	 *  main( 1 number) : decide if it is prime. 
    	 *  main( 101;143,155 ) -&amp;gt; test these numbers
    	 *  main( 101 10000 ) -&amp;gt; test 101 using cache of 10000
    	 *  main( 101,143,155 10000) -&amp;gt; test these numbers) using cache of 10000
    	 * 
    	 * @param args : 0 : number(s) to test for , by default 1511
    	 *               1 : the cache, by default 10000
    	 */
    	public static void main(String[] args) {
    		/*
    		 * if there were no arguments:
    		 */
    		int cache = 100; //default amount of digits each number
    		Vector test = new Vector();
     
    		/*
    		 * process the arguments and set up
    		 */
    		if (args.length == 0){
    			test.add( 1511 );// default number of primes printed
    			System.out.println(&quot;Running main without arguments.&quot;);
    			System.out.println(&quot;arg[0] -&amp;gt; number to test set to &quot;+ test );
    			System.out.println(&quot;arg[1] -&amp;gt; cache set to &quot;+ cache );
    		}else{
    			/*
    			 * process the number(s) to test
    			 */
    			String[] parts = args[0].split(&quot;,;&quot;);
    			test = new Vector( parts.length);
    			for(String part : parts){
    				if(part.trim().length()&amp;gt;0){
    					//program will crash on non-numbers.
    					Integer t = Integer.parseInt( part.trim());
    					if(t&amp;gt;1)
    						test.add( t );					
    				} //no warning, just ignore illegal numbers
    			}
     
    			/*
    			 * compute the cache or read it from second arg:
    			 */
    			int maxt=0; //first &quot;normal&quot; prime is 2&amp;gt;0.
    			for( int t : test){
    				if (t&amp;gt;maxt) maxt=t;
    			}
     
    			if(args.length&amp;gt;1){
    				//for an array of 100, 99 is the max number to test:
    				cache= Integer.parseInt( args[1] );
    				if (cache=max(test)
     
    		/*
    		 * output
    		 */
    		System.out.println(&quot;Cache set to &quot;+cache+&quot;...&quot;);
    		if(test.size()==1){
    			int t = test.get(0);
    			long start = System.currentTimeMillis();
    			boolean isPrime = new CachedPrimes(cache).isPrime( t );
    			long delta = System.currentTimeMillis()-start;
     
    			System.out.println(&quot;Testing &quot;+t+&quot; -&amp;gt; is &quot; + (isPrime ? &quot;not &quot; :&quot;&quot;) + &quot;prime&quot;);
    			System.out.println(&quot;Setting up cache of &quot;+cache+&quot; numbers took &quot;+delta+&quot; ms&quot;);
     
    		} else{
    			long start = System.currentTimeMillis();
    			CachedPrimes cp = new CachedPrimes(cache);
    			long delta = System.currentTimeMillis()-start;
    			System.out.println(&quot;Setting up cache of &quot;+cache+&quot; numbers took &quot;+delta+&quot; ms&quot;);
     
    			System.out.println(&quot;Testing &quot;+test.size()+&quot; numbers for primeness...&quot;);
    			for(int t: test ){
    				System.out.println(t+&quot; -&amp;gt; &quot; + (cp.isPrime(t) ? &quot;not &quot; :&quot;&quot;) + &quot;prime&quot;);
    			}
     
    		}
     
    		CachedPrimes.resize(10);
    		CachedPrimes.isPrime(-1);
    		CachedPrimes.isPrime(1);
    		CachedPrimes.resize(150);
    		System.out.println( &quot;   9 &quot; + CachedPrimes.isPrime(9) );
    		System.out.println( &quot;  11 &quot; + CachedPrimes.isPrime(11) );
    		System.out.println( &quot;1111 &quot; + CachedPrimes.isPrime(1111) );
    		System.out.println( &quot;1113 &quot; + CachedPrimes.isPrime(1113) );
    		System.out.println( &quot;1117 &quot; + CachedPrimes.isPrime(1117) );
    	}//~main
     
    }//~class CachedPrimes
  • 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

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

  • http://shivpratap.com 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 &amp; 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;
    	}
  • ashish
    private void generatePrimeLessThan(int x){
    int number[] = new int[x];
    int i=0;
    int j=0;
    boolean isPrime = false;
    for(i=0;i&amp;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&amp;lt;number.length;i++){
    if(number[i]==1){
    System.out.print(i+&amp;quot; &amp;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&amp;lt;number.length;i++){
    System.out.print(number[i]+&amp;quot; &amp;quot;);
    }
    }
  • 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 &amp;&amp; primer%2 == 0 )
              return false;
         else
         {
              for( i = 3; i &lt; primer; i += 2 )
              {
                   for( j = i; j &lt; primer; j += 2 )
                   {
                        k = i * j;     /*I incorrectly wrote this outside the loops */
                        if( k == primer )
                             return false;
                   }
              }
     
              return true;
     
         }
    }
    • AU
      public static boolean isPrime ( int num )
        {
          boolean prime = true;
          int limit = (int) Math.sqrt ( num );  
       
          for ( int i = 2; i &lt;= limit; i++ )
          {
            if ( num % i == 0 )
            {
              prime = false;
      	break;
            }
          }
       
          return prime;
        }
      • kosterix

        Fails on -1.
        Fails on 1000*1000*1000.
        Performance also horrible.

  • 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

    • http://www.mkyong.com mkyong

      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.

  • 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 &lt; 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;
    	int k = 0;
     
    	if( primer  < 1)
    	else if ( primer == 2 )		
    		return true;				/*2 is the only even prime*/
    	else if ( primer % 2 == 0 &amp;&amp; primer &gt; 2 )
    		return false;				/*every other prime is odd*/
    	else
    	{
    		k = i * j;
    		for( i = 3; i <= primer; i += 2 )
    		{
    			for( j = i; j < primer; j += 2 )
    			{
    				if( k == primer )
    					return false; 	/*not all odds are primes*/
    			}
    		}
    	}
     
    	return true;					/*when value of primer IS prime*/
     
    }

    // Although this method is effective, as it works for any valid integer input to the method isPrime(), it is inefficient, due to the for loops nested within the if-else statement. A better solution would be to make isPrime() a recursive method.//

  • Alex Sales

    only solution 1 is correct ~_~

  • http://twitter.com/Mexflubber 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.

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

  • BlogReader

    Or use BigInteger.isPrime()

    • kosterix

      No.
      BigInteger will fail on heap space if cached and on performance if computed.

      • kosterix

        Also the primes > Integer.MAX_VALUE is infinite, so please specify what you really want.

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

  • Jose Luis Montes de Oca

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

    • annoying

      shut up dumb ugly c.un.t

    • magicsign

      Second solution is a total fail ! Damn how can you publish such things without having them tested .

      • ChenZi

        This should work.

        private static boolean isPrime(int num) {
        int upLimit = (int) Math.sqrt(num);

        for (int i = 2; i <= upLimit; i++) {
        if (num % i == 0)
        return false;
        }

        return true;
        }