## Sunday, May 03, 2009

### JavaOne Talk: Prime Sieve

Next month I am speaking at JavaOne on the performance of various programming languages running on the JVM. For the talk, I am taking several algorithm/programming problems solved in each of the various languages, and comparing the relative performance and tuning tips. For each problem, I am using "native Java" as a reference point. This is the first of many blog posts that show these various programming problems solved in the various languages. I am posting these programs as a way for other folks to let me know where I've screwed up, i.e. done something that will negatively affect performance, etc.

I am not too interested in significantly different ways to solve these problems. For example, the first algorithm is a prime sieve. So I would not be interested in somebody letting me know that there are other ways to generate primes besides a sieve. However, I am interested in finding mistakes in my implementations. I will not claim to be an expert in any of these languages -- in fact I have been learning two of the languages, Fan and Clojure, specifically for this talk -- so there is a good chance that I did screw something up. Even in the languages that I'd like to think I am pretty good at (including Java), I figure there is always a good chance of me doing something screwy there too. So without further ado, here is my prime sieve in Java.

`import java.util.Arrays;// calculates the first n primespublic class Primes {    final private int[] primes;    private int cnt = 0;        public Primes(int n){        primes = new int[n];        init();    }    private void init(){        int i=2;        int max = calcSize();        boolean[] nums = new boolean[max];        Arrays.fill(nums, true);        while (i < max && cnt < primes.length){            int p = i;            if (nums[i]){                // add it to the list of primes                primes[cnt++] = p;                int j = 2*p;                // remove all the multiples of the prime                while (j < max - p){                    nums[j] = false;                    j += p;                }            }            i += 1;        }    }    public int last(){        return primes[cnt-1];    }    // calculates number of integers needed to find n primes    private int calcSize(){        int max = 2;        while ((max/Math.log(max)) < primes.length && max < Integer.MAX_VALUE && max > 0){            max *=2; // memory inefficient, but fast        }        return max;    }}`