π π β 8530092
β· I.e. 0b100000100010100010101100: for all primes π β€ 23,
TestBit(π π, π) = true
if π β€ 23 then
β· Quick check for small values, simpler and faster
than testing equality on each option
return TestBit(π π, π)
end if
if Β¬TestBit(π, 0) then return β₯
β· I.e. π is even and, as per line 2, π > 2 thus composite
end if
And it indeed is a bug. The function guarantees to return false βif the number can be determined to be compositeβ and true for all primes, so it should err in only one way.
I would further improve the code by having it shortcut for all primes smaller than 31 (adding 29 and 31) or 63.
I would further improve the code by having it shortcut for all primes smaller than 31 (adding 29 and 31) or 63.