Задача
Кристиан Гольдбах показал, что любое нечётное составное число можно записать в виде суммы простого числа и удвоенного квадрата.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
Оказалось, что данная гипотеза неверна.
Каково наименьшее нечетное составное число, которое нельзя записать в виде суммы простого числа и удвоенного квадрата?
Решение
Решение сделал дубовое, с целью потом его оптимизировать чем-то вроде решета Эратосфена, но это не понадобилось. Задача решилась легко и быстро (но есть нюанс).
Начнём перебор с простого числа, для которого результат уже известен, например 31 из условий задачи. Следующее число чётное, его проверять не надо. Следующее – 31 + 2, т.е. всегда будет подтверждать гипотезу; следующее опять чётное.
То есть двигаться надо, прибавляя по 4 к каждому следующему простому числу. Если простое +4 не даёт нам опять простое, тогда оно кандидат на проверку гипотезы. После проверки двигаемся уже с шагом не +4, а +2, перебирая нечётные числа, пока опять не встретим простое.
Проверку делаем так: из текущего числа вычитаем сначала 2*1^2, потом 2*2^2, и так до тех пор, пока остаток не станет простым. Если же остаток стал меньше 2, значит простым он так и не стал, и это является опровержением гипотезы Гольдбаха.
Теперь про нюанс. Вот первый вариант кода задачи:
Выглядит компактно и выдаёт верное решение, но, как оказалось, по чистой случайности. Я каждый раз прибавляю 4 к текущему числу, вне зависимости от того, простое оно или нет. Но работает это только когда начальное n равно 33 (что я выбрал наобум и неправильно, так как оно даже не простое). Тем не менее, именно так работает. Что само по себе довольно интересно.
С учётом разной длины шага код код получается уже такой:
Ссылка на онлайн-компилятор языка C с текстом программы
Ну и вообще говоря, вся эта возня с +4 или +2 это экономия на спичках. Можно прибавлять просто +2, и производительность никак ощутимо не пострадает. Что ж мне теперь, убирать это всё?
Подборка всех задач:
