4 ms·

Divisibility by any n is a walk on a graph with n nodes, each one representing one of the modulus equivalence classes 0 .. n-1.

• jowiar 15y ago
  And there are graphs going either way, either starting from most or least significant digit. (Take previous modulus, *10 mod N, + next digit mod N), or (Take previous modulus, + 10^(next digit) mod N)
  • recursive 15y ago
    In the case of least significant to most significant, that means you need more nodes, because the position of the current digit is another piece of state you also have to keep track of.
    • jowiar 15y ago
      Yes - you need to work powers of 10 modulo the divisor as well.