Yet another prime number generator

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),Integer.parseInt(args));
}

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

}

}

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

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++) {
}
}

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;
}
}
• It is dangerous to use an ArrayList as a cache, as soon as the cache gets used by more than one thread. – Roland Illig Jun 22 '14 at 20:03

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.

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()
{
String bigNumber = "";
System.out.print("Please enter an integer value (1 to quit): ");
try
{
}
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
• Hi, and welcome to code review. You should consider posting your code as a question, and get it reviewed. – rolfl Jun 22 '14 at 14:09
• 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 Jun 22 '14 at 15:18
• 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. – Mark Ross Jun 24 '14 at 2:38
• What We meant is that you should ask the code as a new question ;-) (Which I still think you should consider) – rolfl Jun 24 '14 at 2:42
• Ok, I posted the code under a separate question. Feels a bit redundant, though. – Mark Ross Jun 24 '14 at 6:48

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.