25

Чтобы узнать, является ли простым некоторое число N, надо просто делить его по очереди на числа 2, 3, 5, 7, … до тех пор, пока или одно из них не разделит N нацело, что будет означать, что N не простое, или… или что? Как узнать, когда остановиться? Ответ: остановиться надо, когда простое, на которое вы собрались разделить, оказывается больше, чем √N.Если, скажем, N равно 47, то √N = 6,85565…, так что надо проверить только делимость на 2, 3 и 5. Если ни одно из них не делит 47, то, значит, 47 — простое. Почему не надо проверять 7? Потому что 7×7 = 49, так что, если бы число 7 точно делило 47, частное было бы каким-то числом, меньшим 7. Аналогично, √701000 равен 837,2574. Последнее простое число ниже этого равно 829, а следующее простое выше этого есть 839. Если бы 839 делило 701000, то частное было бы числом, меньшим 839 — или некоторым простым, меньшим 839 (которое, следовательно, уже было проверено), или же составным, равным произведению еще меньших простых сомножителей…