Monday, May 18, 2009

JavaOne Talk: Fan Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

Note: This solution is courtesy of Mr. Fan himself, Brian Frank. Thanks Brian!

class Primes {
Int[] primes := Int[,]
Int size

new make(Int n) {
size = n
primes.capacity = n
init
}

private Void init() {
i := 2
max := calcSize
nums := Bool[,]
nums.fill(true, max)
while (i < max && primes.size < size) {
p := i
if (nums[i])
{
primes.add(p)
j := 2*p;
while (j < max - p) {
nums[j] = false
j += p;
}
}
i += 1;
}
}

Int last() { primes.last }

private Int calcSize() {
max := 2
while ((max.toFloat/max.toFloat.log).toInt < size && max < 0x7fff_ffff && max > 0) {
max *=2; // memory inefficient, but fast
}
return max;
}
}

No comments:

Post a Comment