функция и простые числа

[kidasert]

написать функцию, которая по данному натуральному числу $N$ находит максимальное число $K$ такое, что $N$ делится на $p^K$, где $p$-простое число

какую вообще идею использовать?
перебирать все простые числа, начиная с двойки? и если делится, то запускать функцию для числа $\frac{N}{p^k}$ ?

например, пусть $N=32$
и начать с $p=2$. 32 делится на 2. и дальше давать на вход уже число 16. оно опять делится на 2. и так далее. В конце получится, что $k=5$.

Или можно еще какую-то более рациональную идею использовать?

-- 25.07.2017, 01:29 --

по идее можно факторизовать число. но для факторизации нет эффективного алгоритма

[mihaild]

mathworld говорит, что уже проверка $K > 1$ может оказаться не проще факторизации.

[kidasert]

то есть проще просто факторизовать обычным самым алгоритмом перебора.

[mihaild]

Для факторизации существуют более сложные и гораздо более эффективные на практике алгоритмы, чем лобовой перебор. Вопрос в том, для каких чисел вы это собираетесь решать на практике.

[Евгений Машеров]

Зависит, конечно, от того, какие числа, может, N это числа специального вида в длинной арифметике. Но лично я бы тупо шёл бы по списку простых чисел, запоминая рекорд делимости $K_R$, и оборвал бы перебор на простом $p_i$, когда $p_i^{K_R}>N$

[grizzly]

Евгений Машеров в сообщении #1236005 писал(а):

когда $p_i^{K_R}>N$

А после каждого $p_j$, делящего $N$, можно правую часть указанного неравенства проверки уменьшать в $p_j^{k_j}$ раз.

[Евгений Машеров]

Уменьшать автоматически - нет, но проверить делимость на $p_i^{K_R}$ можно. Если делится, проверить, не делится ли дальше, то есть не надо ли рекорд обновить.

[grizzly]

Евгений Машеров в сообщении #1236048 писал(а):

Уменьшать автоматически - нет

Я не совсем понял Вас, Вы -- меня. Может так сторгуемся: когда обнаруживаем очередной рекорд делимости $p_r^{K_r}$, мы бесплатно можем вместо $N$ далее рассматривать $N/p_r^{K_r}$; при этом $p_i$ продолжаем далее по возрастанию, конечно.

[Евгений Машеров]

Так не обязательно делить на рекорд. При любой проверке делить и хранить частное.