Tuesday, November 11, 2008

primes in a bit array

Primes up to 2^12


const unsigned int primes[] = {
0x76d32d26, 0x5948b681, 0x4c325261, 0xb0416984, 0x932c205a, 0x04869125,
0x22886194, 0x8b411452, 0x0c02424c, 0x84992c10, 0xd260a442, 0x21125128,
0xa0420c36, 0x102d02d0, 0x05108a48, 0x149120a6, 0x190c3201, 0x69224801,
0x84424882, 0x93208403, 0x4cb41900, 0x00922010, 0x81691641, 0x0da41044,
0x12914502, 0x9a642009, 0x6002c20c, 0x22490096, 0x08411010, 0x25b08248,
0x06030024, 0x4b448610, 0x2120d841, 0x80cb0880, 0x40052203, 0x44068928,
0x30026520, 0x4b290490, 0x29044a00, 0x10084532, 0x0041808a, 0x0810d125,
0xa4590c22, 0x810832c0, 0x40a44a01, 0x10922104, 0x0a4c0018, 0x45028824,
0x14802180, 0x80058250, 0x48a2006c, 0x10006494, 0xc1418603, 0x01200808,
0xb6004412, 0x1a643043, 0x08129124, 0x041a04a2, 0x11240098, 0x40a40308,
0x16102880, 0x534c1401, 0x0020d264, 0x00c80906
};

int is_prime(unsigned int n)
{
if (n < 2) return 0; /* not prime */
if (n == 2) return 1; /* 2 is prime */
if ((n & 1) == 0) return 0; /* no other even is */

n >>= 1; /* bit array holds odds */

return (primes[n / 32] & (0x80000000 >> n % 32)) != 0;
}

No comments: