DAS ist das Problem

Im Prinzip kann man ja in kleinen, mehreren Schritten kürzen und kommt letzlich auch zum Ziel. Ich würde es vielleicht so angehen :

Zahlen, die auf 0,2,4,6,8 enden sind durch 2 teilbar
Zahlen, der Quersumme eine durch 3 teilbare Zahl ergibt, sind durch 3 teilbar,
Zahlen, die auf 0 oder 5 enden, sind durch 5 teilbar.

Damit kommt man schon mal ein ganzes Stück weiter und kann dann - eben schrittweise - kürzen, bis es nicht mehr geht.