Процессы и алгоритмы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Дано натуральное число 
Докажите, что число 
может быть представлено в виде произведения десяти натуральных чисел
таких, что среди них нет ни одного составного числа, большего 
Подсказка 1
Для начала давайте разложим хоть как-нибудь на 10 множителей. Придумайте какой-нибудь способ разложения.
Подсказка 2
Например такой: 1 * 1 * 1 ... * n. Попробуйте придумать процесс, который будет уменьшать делитель, который больше чем 10⁴, но при этом не будет увеличивать количество делителей больших, чем 10^4.
Подсказка 3
Также надо еще придумать, как объединять некоторые делители. Давайте будем объединять множители, которые в произведении дают не больше, чем 10⁴. Теперь попробуйте описать полностью процесс и понять, что произойдёт.
Подсказка 4
Процесс такой. Если есть множитель больший 10⁴ и произведение каких-то двух меньше 10⁴, их объединяем, а делитель больший 10⁴ раскладываем на два не единичных множителя так, чтобы один из них был меньше 10⁴ (считаем, что у n нет простого делителя >10⁴). Может ли после окончания нашего процесса остаться делитель, который больше 10⁴?
—
Подсказка 5
Правильно, не может! А что надо сделать, если у n есть простые делители, которые >10⁴?
Давайте рассмотрим тривиальное (
) разложение на 
множителей. Пусть у 
нет простых множителей больших 
И
будем делать следующее: если есть множитель больший 
и произведение каких-нибудь двух множителей 
то объединяем их в
один, а потом раскладываем множитель больший 
на два не единичных (один из которых меньше 
Очевидно, что этот алгоритм
закончится в силу того, что у 
конечное количество множителей. Теперь докажем, что когда алгоритм закончится, у нас все множители
меньше 
Пусть не так. Тогда есть множитель больший 
при этом произведение любых двух больше, чем 
следовательно, все
произведение хотя бы 
(
берется из того, что у нас есть 
множителей, попарные произведения
которых больше 
а, значит, их произведение хотя бы 
Противоречие. Если же число 
имеет простой
делители, которые хотя бы 
то поделим на них и будем действовать абсолютно аналогично, но для меньшего количества
множителей. Пусть их было 
Тогда финальная оценка превращается в 
что легко понять больше, чем
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
