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 primes

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

}

}

## No comments:

Post a Comment