Дистанционная подготовка: Превышено максимальное время работы(?).
Превышено максимальное время работы(?).
от Никита Пушкин - Пятница 3 Октябрь 2014, 17:59
148. Разложение на простые
  Написал программу, но сайт пишет, что не все тесты прошли по времени. Неужели можно как-то ускорить ее выполнение?
Re: Превышено максимальное время работы(?).
от Peter Cherepanov - Пятница 3 Октябрь 2014, 18:26
  Можно. Что известно про наибольший простой делитель составного числа меньшего N ?
Re: Превышено максимальное время работы(?).
от Никита Пушкин - Воскресенье 12 Октябрь 2014, 21:45
  Что он не больше корня из n.
Но у меня другой алгоритм. Я просто увеличиваю счетчик, и пока n>1, делю n на это число и записываю его как новый простой делитель. Разве алгоритм в разборе будет быстрее?
Re: Превышено максимальное время работы(?).
от Peter Cherepanov - Понедельник 13 Октябрь 2014, 02:03
  Сколько итераций выполнит ваш алгоритм если число простое?
Re: Превышено максимальное время работы(?).
от Никита Пушкин - Пятница 17 Октябрь 2014, 15:45
  Да, что-то не подумал. Спасибо за подсказку!