Алгоритм (в переформулированном для удобства доказательства виде): "Пока это возможно, мы выбираем из множества минимум A и максимальное число B, такое, что A * B <= N, и заменяем их на их произведение".

Примем без доказательства (т.к. оно может быть нетривиальным) следующие интуитивные утверждения:
1. Для любых двух соседних простых чисел P1, P2 найдется другое простое число P3, такое, что P2 < P3 < P1 * P2.
2. Пусть у нас на каком-то шаге алгоритма есть множество натуральных чисел. Если мы заменим какое-либо число на меньшее, то ответ у нас не ухудшится.
3. При выполнении нашего алгоритма у нас никогда не возникнет ситуации, когда для A и B (из описания алгоритма) будет существовать такое C > A, что C * B <= N.

Из утверждения 3 прямо следует, что если мы ничего не сделаем с A, то мы ухудшим ответ. Из него же следует, что A * B * С > N, так что полученное нами произведение A * B останется во множестве навсегда, а также то, что если мы умножим A на любое другое число C < B, то B у нас тоже останется во множестве навсегда. По утверждениям 1, 2 и вышеописанным следствиям имеем, что если мы заменим A и B на A * B ответ у нас будет явно не хуже, чем если бы мы заменили A и C на A * C или вообще ничего не заменили, что и требовалось доказать.