3 ms·

You're doing all the work of dividing by 7. There are shortcuts to checking divisibility [1] - 2, 3, 5, & 9 have the easiest shortcuts - but 7 is a complicated

• eru 16y ago
  No, he's not doing the work of dividing by seven. That would need memory of around the same size as your number of digits of your input number. His state machine only reads one digit at a time and only needs to store a less-than-one-digit state. My regular expression is a joke on the usual divisibility rules. By the way, you can find your own divisibility rules. They are actually easy to find and prove, if you know a bit about cyclic groups / calculating with modulo. E.g. the rule for divisibility by F in hexadecimal is the same as the one for 9 in decimal. Divisibility by 11 or 101 or 1001, or 9, 99, 999 is also really simple.