Циклы · 16 из 33
Разложить на простые
Лабораторная «циклы», задание «разложить на простые множители». Борис Аркадьевич диктует простое число 1 000 000 007 и смотрит на часы: перебор делителей до самого числа — миллиард шагов, до перемены не кончится, а до корня из него — тридцать тысяч, меньше секунды. Почему корня хватает, он спросит на защите.
Что сделать
Разложите число на простые множители, перебирая делители, пока их квадрат не больше оставшегося числа.
Что приходит
n— натуральное число, от 1
Что вернуть
Список простых множителей по возрастанию, с повторами: 12 → [2, 2, 3]; у единицы — [].
Допишите функцию mnozhiteli в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
mnozhiteli(360)
[2, 2, 2, 3, 3, 5]
Делитель d начинается с 2. Пока d · d не больше оставшегося числа: пока число делится на d, записываем d и делим; потом переходим к d + 1.
Когда цикл кончился, оставшееся число, если оно больше 1, — тоже простой множитель, и он записывается последним.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.