uwi uses this function to find prime numbers.This works to n=10^8 in 1 second. Can someone explain in detail?
public static int[] sieveEratosthenes(int n) {
if(n <= 32){
int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
for(int i = 0;i < primes.length;i++){
if(n < primes[i]){
return Arrays.copyOf(primes, i);
}
}
return primes;
}
int u = n + 32;
double lu = Math.log(u);
int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
ret[0] = 2;
int pos = 1;
int[] isp = new int[(n + 1) / 32 / 2 + 1];
int sup = (n + 1) / 32 / 2 + 1;
int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
for(int tp : tprimes){
ret[pos++] = tp;
int[] ptn = new int[tp];
for(int i = (tp - 3) / 2;i < tp << 5;i += tp)
ptn[i >> 5] |= 1 << (i & 31);
for(int i = 0;i < tp;i++){
for(int j = i;j < sup;j += tp)
isp[j] |= ptn[i];
}
}
// 3,5,7
// 2x+3=n
int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4,
13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 };
int h = n / 2;
for(int i = 0;i < sup;i++){
for(int j = ~isp[i];j != 0;j &= j - 1){
int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
int p = 2 * pp + 3;
if(p > n)
break;
ret[pos++] = p;
for(int q = pp;q <= h;q += p)
isp[q >> 5] |= 1 << (q & 31);
}
}
return Arrays.copyOf(ret, pos);
}