Java Prime Number Hunter

New Articles

The PHP Java Extension

JSP File upload progress bar.

LPI Certification

The following code is an Implementation of the Sieve of Eratosthenes written using Java. It's purpose is to sieve the natural numbers and separate the primes from the composites. On this site you will find a PHP implementation as well as MySQL stored procedure that implements this algorithm. This code is much much faster than both those.

public class Eratosthenes
{
    int max;
    int primes[];
    
    public static void main(String args[])
    {
        Eratosthenes erat = new Eratosthenes(10000000);
        erat.find_primes();
    }
    public Eratosthenes(int max)
    {
        this.max = max;
    }
    
    public void find_primes()
    {
        int i,j,k, divisor, offset;
        
        double sqrt = Math.sqrt(max)+1;
        int tmp[];
        
        if(max  > 100)
        {
            primes = new int[max/2];
        }
        else
        {
            primes = new int[max];
        }
        primes[0] = 2;
        primes[1] = 3;
        
        for(i=2,j=5; j < max ; j+=2)
        {
            if(j % 3 != 0)
            {
                primes[i++] = j;
            }
        }
        
        for(i=2, divisor=5, offset = primes.length; divisor < sqrt ; )
        {
            j = i*i;
            tmp = new int[offset];
            offset = j;

            /* 
             * Copy the numbers that have already been sieved to a new array.
             */
            System.arraycopy(primes,0,tmp,0,j);
            while( j < tmp.length)
            {
                k = primes[j++];
                if(k==0)
                {
                    /*
                     * The array may contain some zeros at the end. It's too much 
                     * trouble to calculate the exact size for the array. Easier
                     * to pad with zeros
                     */
                    break;
                }
                if(k % divisor != 0)
                {
                    tmp[offset++] = k;
                }
            }
            primes = null;
            primes = tmp;
            tmp = null;
            divisor = primes[i++];
        }
    }
}

For completeness sake you can dump the numbers to a file. But this code is so fast, that reading from disk would be slower for small numbers.

    try
    {
        File f = new File("/dev/shm/primes.txt");
        FileWriter writer = new FileWriter(f);
        writer.write(Arrays.toString(primes));
        
    } catch (IOException ex)
    {
        ex.printStackTrace();
    }

Like the PHP version, this code also happens to be a memory hog. if you want find primes larger than about 10,000,000 you will need to change the amount of memory allocated to the JVM. If that is not an option, you can change the first for loop (the one that populates the array) so that numbers divisable by 5,7 and 11 are also left out. That would reduce the memory consumption by a little bit.

Copyright © Raditha Dissanayake 2013