53
правки
Изменения
Нет описания правки
Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''':
<code>
A = {};
'''while''' (n > 1) { '''if''' (!f(n, n)) { //''если число простое - добавляем его в список делителей и завершаем цикл'' {
A.add(n);
n = 1;
'''break''';
// ''Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R''
R = n;
L = 2;
'''while''' (R > L + 1) { //''находим наименьший простой делитель'' {
c = (L + R) / 2;
'''if''' (f(n, c))
'''else'''
L = c;
A.add(L);
n = n / L;
'''return''' A;
</code>
