After all that about how we humans working in base 10 can quickly test divisibility by some small primes by some ingenious tricks... who cares about base 10? Think binary so you can be cool. * N divisible by 2 <==> has a zero at the end <==> (N&1)==0. * Note that 63 = 3*3*7. If you add the consecutive 6-bit blocks of N together, result is congruent to N mod 63. Similarly for other 2^k-1 such as 3, 7, 15=5*3, 31=prime, 63=3*3*7, 127=prime, 255=5*3*17, 511=7*73 etc. * Note that 65=5*13. If you add and subtract alternately the 6-bit blocks of N then you get something congruent to N mod 65. Similarly for other 2^k+1 such as 33=3*11, 129=3*43, 257=prime, 513=3*3*3*19 etc. The numbers 2^k +- 2^j +- 1 would seem to be particularly important for this kind of game. The numbers 2^(2^k)-1 are especially important since computer wordlengths are powers of 2, and they have a lot of nice factors. Related question to "Can we make fast divisibility tests for binary computers?" is "...and should anybody really want to?"