> The algorithm must work at least for integers in the range 1-1000. We do not care for numbers outside that range.

In that case, a list of 1000 strings should work just fine. Fast lookup and can accommodate any new rule that comes in.