Поттер взял почти самый тупой алгоритм из возможных, и попробовал использовать его. "Почти" потому что всё же с небольшими улучшениями -- он не стал перебирать пары чисел от 2 до sqrt(n), он воспользовался знанием того, что оба множители трёхзначные. И он не стал перебирать трёхзначные числа, вычеркнув оттуда нечётные. И это всё.
По-хорошему, имея на руках произведение и список трёхзначных простых чисел, можно посмотреть на последнюю цифру произведения и сделать вывод о том, какими должны быть последние цифры исходных множителей. 181429: девятку на конце можно получить либо умножая 3 на 3, либо 7 на 7, либо 9 на 1. Вычеркнуть вообще какие-нибудь числа из рассмотрения это, увы, не позволит, потому что среди трёхзначных простых чисел нет таких, которые бы заканчивались не на 1, 3, 7, 9, но если мы в процессе перебора возьмём для рассмотрения число 113, то в качестве дополнения к нему надо рассматривать только те, которые заканчиваются на 3. И рассматривая их надо помнить, что мы пытаемся найти точку кривой x*y=181429, за счёт этого можно резко сэкономить на проведении реальных арифметических действий, выполняя максимум одно умножение трёхзначных чисел для каждого простого числа. Если же с устным счётом швах, то да, можно все эти сложности заменить делением в столбик, как предложил bore.
Но Поттер намеренно выбрал тупой алгоритм. Потому что его задачей было не найти два множителя, а заставить маховик времени найти эти множители. А это значит, что Поттер должен выполнять O(1) действий, а маховик всё остальное. Поэтому Поттер не стал выполнять деление -- оно само по себе, как минимум O(log n), где n -- это число, которое надо разложить (на самом деле скорее O(log
2 n), потому что на каждом шаге деления придётся производить умножение). Поэтому же Поттер тщательно построил алгоритм поиска так, чтобы тот перебирал бы ~200k пар чисел. Он ведь
намеренно выбирал задачку посложнее, задачку в которой перебора побольше.
Ему стоило попробовать что-нибудь попроще. Взять в качестве арифметического действия не умножение (на которое мозг натаскан и подсказывает ответы автоматически), а, допустим, возведение в куб по модулю N, где N -- это небольшое простое число: 5, 7, 9, 11, 13... Соответственно загадывается число от 2 до N-1, возводится в куб и берётся остаток от деления на N. Поттер знает куб, но не само число. После чего его задача угадать. Правда действуя таким образом шесть раз в сутки он бы быстро задолбал Антони так, что тот бы полез морду бить, но зато можно было бы измерить: при каком N начинает вылезать "НЕ ШУТИ СО ВРЕМЕНЕМ" вместо ответа. Ещё лучше было бы соорудить механизм, который бы делал это -- поведение человека зависит от многих факторов, и один и тот же человек в одной и той же ситуации может повести себя по разному, в зависимости от того, что он ел на завтрак. Поэтому лучше конечно было бы использовать механизм. Правда я не знаю какой именно: электроника в Хогвартсе не работает, поэтому программируемый калькулятор (смартфонов тогда не было ещё) не удалось бы использовать в этих целях, а собрать механический возводитель в куб по модулю... Это задачка инженеру на полгода, а то и на год, но не Поттеру.
Кстати, что заставило Гарри написать дрожащей рукой "НЕ ШУТИ СО ВРЕМЕНЕМ"?
Написать "НЕ ШУТИ СО ВРЕМЕНЕМ" его заставила надпись "НЕ ШУТИ СО ВРЕМЕНЕМ".
Ведь он твердо решил изменять прошлое, отправляя обратно бумажку с другой надписью, чем он получил.
Скажем, если бы он получил 347*653, что бы он сделал?
А фишка в том, что он не получил бы 347*653. Это запрещено законом самонепротиворечивости Вселенной. Если бы его решение отправить назад в прошлое изменённые числа было бы не столь решительным, если бы он мог бы передумать, то может быть он получил бы 347*653 и тогда бы он передумал и отправил бы в прошлое эти самые два числа не изменяя их. Но, видимо, он был твёрдо настроен и только внешний толчок мог его сдвинуть с идеи отправить назад в прошлое не ту информацию, которую он получил, а другую.
