|
Разложение на простые множители
(Время: 1 сек. Память: 16 Мб Сложность: 27%)
Для решения данной задачи можно найти все простые числа, не превосходящие sqrt(n), а далее делить на каждое из них число n пока оно делится, изменяя значение n. Но на самом деле вовсе не обязательно осуществлять поиск простых делителей, достаточно это проделывать со всеми числами от 2 до sqrt(n) в порядке возрастания. При этом, каждый раз при изменении значения n следует бежать до нового значения sqrt(n) для того, чтобы в итоге в n оказалось единственное простое число. Описанный выше алгоритм можно представить в следующей форме:
read(n)
i=2
while(i<=sqrt(n))
if(n mod i=0){
write(i)
n=n div i
if(n>1) write('*')
}
else i=i+1
if(n>1) write(n)
| |
