Yet another prime number generator

Question

The question asked to find all the prime numbers within a particular range. The way I approached this was to loop through each of the numbers within the range and for each number check whether it's a prime. My method for checking prime is to start at 3 and loop till number/2 in hops of 2 (essentially excluding all the even numbers).

Can somebody take a look at the code an tell me how I might be able to better this snippet and what are some of the aspects that I am missing?

public class PrimeBetween{
public static void main(String[] args){
 printAllPrimes(Integer.parseInt(args[0]),Integer.parseInt(args[1]));
}
public static void printAllPrimes(int start,int end){
 for(int i = start;i <= end;i++){
 if(isPrime(i))
 System.out.println("Print prime:"+i);
 }
}
private static boolean isPrime(int i){
 if(i%2 == 0 && i!=2)
 return false;
 else{
 if(i == 1) return false;
 for(int p=3;p<=i/2;p+=2){
 if(i%p == 0)
 return false;
 }
 return true;
 }
}
}

Answer 1

Well, for starters, it is a proven mathematical fact that if a number is prime, it is not divisible by any prime number that is less than its square root. In your inner loop you go up to i/2 and you can change this to Math.floor(Math.sqrt(i)).

Because you are checking for a range of numbers, you would probably benefit from a cache of primes, rather than testing every odd number less than the square root.

Something like this:

package mypackage;
import java.util.ArrayList;
/**
 * Checks for primeness using a cache.
 */
public class PrimeCache {
 private static ArrayList<Integer> cache = null;
 static {
 cache = new ArrayList<Integer>();
 cache.add(2);
 }
 public static boolean isPrime(int i) {
 if (i == 1) return false; // by definition
 int limit = (int) Math.floor(Math.sqrt(i));
 populateCache(limit);
 return doTest(i, limit);
 }
 private static void populateCache(int limit) {
 int start = cache.get(cache.size() - 1) + 1;
 for (int i = start; i <= limit; i++) {
 if (simpleTest(i)) cache.add(i);
 }
 }
 private static boolean simpleTest(int i) {
 int limit = (int) Math.floor(Math.sqrt(i));
 return doTest(i, limit);
 }
 private static boolean doTest(int i, int limit) {
 int counter = 0;
 while (counter < cache.size() && cache.get(counter) <= limit) {
 if (i % cache.get(counter) == 0) return false;
 counter++;
 }
 return true;
 }
}

• Roland Illig: It is dangerous to use an ArrayList as a cache, as soon as the cache gets used by more than one thread.

Answer 2

You could also use the sieve of Eratosthenes so as to improve time complexity. It has a lot of optimizations, you can even reduce the memory footprint by using bit operations, and many others, if you're into maths.

Answer 3

Using a BitSet to hold the numbers is pretty efficient. I've been able to find the primes up to about 2 billion using one. This finds almost 100 million primes in well under a minute.

I can post the code if there is any interest, but I make NO claims for its quality. I also don't claim to be a good object-oriented programmer.

Using Sieve of Eratosthenes logic, you don't have to do ANY dividing. It just isn't required. I also used a BitSet to maximize how many numbers I could check.

I found that I needed a separate loop to 'sieve' out the even numbers higher than 2. The main logic just didn't work for 2.

Also, when marking out the non-primes, you only need to start at the square of the prime you just found. This is because any smaller non-prime will have already been 'sieved' out because it is divisible by a smaller prime, which you will have already found and processed. Also, your increment for the 'sieve' can be 2 times the prime you're sieving for (because the others would be even numbers, so no need to check them).

Here's my implementation:

//package Eratosthenes5;
import java.io.IOException;
import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;
public class Eratosthenes5 {
// This uses a BitSet instead of a boolean array to see
// if this saves any memory. It enables me to test approx.
// 8x as many numbers. 109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion. I've not determined the upper limit, but
// I suspect it is the java max integer size. It finds almost 
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648 
 /**
 * @param args
 * @throws IOException
 */
 public static void main(String[] args) throws IOException 
 {
 int maxSize = 1;
 int maxNumber;
 int maxSearch;
 int primeCount;
 int maxPrime;
 String name;
 name = getTheMaxNumber();
 while (name.compareTo("1") != 0) 
 { 
 long startTime = System.currentTimeMillis();
 maxSize = Integer.parseInt(name);
 maxNumber = maxSize + 1; 
 maxSearch = (int) java.lang.Math.sqrt(maxNumber);
 primeCount = 1; //Start the count at 1 because 2 is prime and we'll start at 3
 maxPrime = -1;
 //use a BitSet array to maximize how many primes can be found
 BitSet numbList = new BitSet( maxNumber );
 numbList.set(0, maxNumber-1, true); //set all bits to true
 numbList.clear(0);
 numbList.clear(1);
 //clear the even numbers (except 2, it's prime)
 for (long k = 4; k <= maxSize; k+=2)
 {
 numbList.clear((int)k);
 }
 // sieve out the non-primes
 for (int k = 3; k < maxSearch; k+=2)
 { 
 if (numbList.get(k))
 { 
 sieveTheRest(k, numbList, maxSize);
 }
 } 
 //Count the primes
 for (int k = 3; k <= maxSize; k+=2)
 { 
 if (numbList.get(k))
 { 
 maxPrime = k;
 primeCount +=1;
 if (primeCount % 1000000 == 0)
 {
 System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "") 
 + ((primeCount/1000000 < 10) ? " " : "")
 + primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
 }
 }
 }
 //we're done
 System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
 System.out.format("array size : %,11d%n", maxNumber);
 // System.out.format("prime count : %,11d%n", primeCount);
 System.out.format("prime count : %,11d%n", numbList.cardinality());
 System.out.format("largest prime found: %,11d%n", maxPrime);
 System.out.format("max factor : %,11d%n \n", maxSearch);
 long stopTime = System.currentTimeMillis();
 System.out.println("That took " + (stopTime - startTime)/1000.0 + " seconds");
 name = getTheMaxNumber();
 }//end of while 
 System.out.println("\nEnd of program");
 }//End of method Main
 /**
 * 
 * @return Passes back a string holding the maximum number to check 
 */
 static String getTheMaxNumber()
 {
 BufferedReader dataIn = new BufferedReader(new
 InputStreamReader( System.in) );
 String bigNumber = "";
 System.out.print("Please enter an integer value (1 to quit): ");
 try
 {
 bigNumber = dataIn.readLine();
 }
 catch( IOException e )
 {
 System.out.println("Error!");
 } 
 return bigNumber;
 }
 /**
 * @param myPrime The latest prime to be found.
 * @param theBitSet The BitSet holding the prime flags
 * @param maxSize The largest index in the BitSet
 */ 
 static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
 {
 for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
 {
 theBitSet.clear((int) k);
 }
 }
}//End of Class eratosthenes5

• rolfl: Hi, and welcome to code review. You should consider posting your code as a question, and get it reviewed.
• Mark Ross: Well, here is my code, but I don't really have any questions about it. It works for me and I've been able to verify my results with some on-line lists of prime numbers.
• Mark Ross: Thank you for the help, Jamal. I'm very new to posting and I struggle trying to figure out how to do things right. I appreciate your help and I would welcome any comments on the code.
• rolfl: What We meant is that you should ask the code as a new question ;-) (Which I still think you should consider)
• Mark Ross: Ok, I posted the code under a separate question. Feels a bit redundant, though.

Answer 4

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number - not every smaller number. This is the siev of Eratosthenes in the form of an array but not only for 2, 3 and five, but every prime number. In fact you only need to check against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {
 int index, candidate;
 int[] primes = new int[targetNumberOfPrimes];
 while (index < targetNumberOfPrimes) {
 if (candidate < 2) {
 candidate++;
 continue;
 }
 if (isPrime(index, candidate, primes)){
 primes[index] = candidate;
 index++;
 }
 candidate++;
 }
 return primes;
}
private static boolean isPrime(int current, int candidate, int[] primes){
 for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
 if (candidate % primes[i] == 0) {
 return false;
 }
 }
 return true;
}

It took my computer about 0.7 seconds for 40000 prime numbers.