Для решения задачи рассмотрим натуральные числа от 1 до 12000000. Пусть они разбиты на пары, так что в каждой паре одно число делится на другое. Если число x x x делится на y y y, то x x x можно представить как k⋅y k \cdot y k⋅y, где k k k — натуральное число. Чем больше одно число, тем меньше возможных делителей у него. Например, для числа n n n мы можем рассмотреть все делители этого числа, но делителей всегда меньше, чем само число. Таким образом, у каждого числа ограниченное количество делителей, что создает ограничения на количество пар. Обозначим количество натуральных чисел от 1 до N N N как N N N. В нашем случае N=12000000 N = 12000000 N=12000000. Если мы попробуем разбить числа на пары, максимально возможное количество пар будет зависеть от условий делимости. Максимально возможные пары составляют менее половины всех чисел, поскольку для каждой пары одно число должно иметь делитель и одно число, на которое оно делится. Это означает, что на каждую пару всегда должно оставаться хотя бы одно неразделенное число. Считаем: если N=12000000 N = 12000000 N=12000000, то максимальное количество пар будет примерно 6000000 6000000 6000000. Следовательно, оставшиеся числа формируют население чисел без пары. Таким образом,