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

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

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.