If what you are seeking is never-fail primality tests, the following is the fastest I have that never fails for 32-bit unsigned integers: uint SmithIsPrime32(uint32 p){ //TRUE iff p is a prime and <=32 bits long. uint hash; if((p&1)==0){ return(p==2); } if( !StrongPsp232(p) ){ return(FALSE); } //base 2 strong psuprime test if(p<2047){ return(TRUE); } if( !StrongPsp32(p, 63778) ){ return(FALSE); } //base 63778 ditto hash = (p*2869299540U)>>25; assert(hash < 128); return(hash63778tab[hash]!=p); //perfect hash table of exceptions } where you need this array const uint hash63778tab[128] = { //these 50 numbers are the only nonprime odd spsp{2,63778} below 2^32: 979363153, 0, 0, 643552909, 0, 8725753, 0, 0, 0, 0, 329153653, 48191653, 0, 8036033, 0, 3116107, 0, 0, 839280691, 0, 450866021, 0, 0, 0, 0, 0, 0, 2269093, 0, 0, 0, 0, 0, 2693739751, 0, 2717428033, 1464568381, 0, 0, 0, 0, 1714322377, 1140573601, 0, 0, 63318169, 0, 0, 4157008813, 0, 0, 220729, 0, 0, 0, 0, 0, 3207297773, 0, 0, 0, 385319089, 1930534453, 0, 0, 0, 1054999441, 787085857, 0, 0, 2017509601, 0, 0, 967287751, 1272866167, 0, 3548378341, 3274264033, 0, 0, 0, 2206095589, 2766006253, 453366029, 176030977, 126132553, 0, 0, 0, 0, 3242533897, 0, 1121176981, 0, 2181961, 0, 0, 17208601, 0, 0, 0, 0, 48316969, 741751, 724969087, 0, 0, 0, 43661257, 0, 0, 0, 0, 0, 0, 1153164097, 1104194521, 0, 3323829169, 0, 765378241, 22591301, 1894909141, 3900327241, 60547831, 0, 1328256247, 0 }; and you also need to code up the strong PSP test (which I did). For 64-bit unsigned integers I also have a never-fail test which on average over all odd numbers takes only about 10% more time. It is somewhat harder to describe though, it involves both a strongPSP (base 2) test and a "Lehmer-Smith test." I can supply C code file. The first pseudoprimes for my 64-bit never-fail tests are not known and probably exceed 10^100 (if they exist, which they probably do).