October 14, 2007

Short n sweet

I came across this algorithm - Sieve of Eratosthenes to generate prime numbers from 2 to n.

public boolean[] sieve(int n)
{
boolean[] prime=new boolean[n+1];
Arrays.fill(prime,true);
prime[0]=false;
prime[1]=false;

int m=Math.sqrt(n);

for (int i=2; i<=m; i++)
if (prime[i])
for (int k=i*i; k<=n; k+=i)
prime[k]=false;

return prime;
}

No comments: