Альтернативным решением для Решета Эратосфена было бы создать тест T (k), который возвращает True или False для любого заданного k.
Это было бы медленнее, но в этом случае хранилище не понадобилось бы,таким образом, он будет легче распространяться на произвольную длину данных.
Если вы на мгновение упростите задачу и скажете, что мы просто пытаемся отбросить отражения, это будет легко:
T_ref(k) returns true iff k <= Reflection(k).
Что касается вращающихся битов, то можно сделать то же самое:
T_rot(k) returns true iff k == MIN{the set of all rotations of k}
Можно подумать о делении целых чисел на группу классов эквивалентности E (k), где E (k) - множество всехперестановки отражения и вращения k.
Возможно, вы захотите потратить немного времени, чтобы убедиться, что множество натуральных чисел N легко разбивается на такие непересекающиеся подмножества.
Тогда множество
{k s.t. k == MIN(E(k)) }
гарантирует, что в каждом классе эквивалентности будет содержаться ровно один элемент.
Это будет действительно хороший вопрос для интервью.