Олимпиады по информатике

[Silent guest]

Готовлю к олимпиадам по информатике и натыкаюсь на следующую задачу с решением на официальном сайте (перечневая олимпиада, то есть дает право на поступление).


Ссылки на первоисточник:
Условие
Решение
Первое же предложение разбора вгоняет в ступор - а куда девать 101, 103 и прочую массу простых чисел? Вопрос к экспертам - в объяснении пропущены какие-то этапы и я его поняла неправильно или оно неверно совсем?

@темы: Образование, Олимпиадные задачи

Comments

[VEk]

куда девать 101, 103 и прочую массу простых чисел?

Все написано верно. ЛЮбое число, не превосходящее 2*10^9 имеет не более 9 простых делителей. Причина объяснена.
Но это не означает, что там не может быть простого делителя 101 или 103 и т.п. Посмотрите 101*103*107*109*113 > 10^10 и в 4-байтовый целый тип не вмещается (а это - первые 5 простых чисел , больших 100).
Вывод, чем больше взятые простые числа, тем меньше их будет в произведении.

[Silent guest]

VEk, спасибо большое, все поняла. Меня сбил пример, показалось что приведен полный перечень возможных простых.