2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 функция и простые числа
Сообщение25.07.2017, 00:25 


24/07/17
2
написать функцию, которая по данному натуральному числу $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 --

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

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение25.07.2017, 01:47 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
mathworld говорит, что уже проверка $K > 1$ может оказаться не проще факторизации.

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение25.07.2017, 02:04 


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

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение25.07.2017, 10:23 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение26.07.2017, 12:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение26.07.2017, 12:52 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Евгений Машеров в сообщении #1236005 писал(а):
когда $p_i^{K_R}>N$
А после каждого $p_j$, делящего $N$, можно правую часть указанного неравенства проверки уменьшать в $p_j^{k_j}$ раз.

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение26.07.2017, 15:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение26.07.2017, 16:32 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Евгений Машеров в сообщении #1236048 писал(а):
Уменьшать автоматически - нет
Я не совсем понял Вас, Вы -- меня. Может так сторгуемся: когда обнаруживаем очередной рекорд делимости $p_r^{K_r}$, мы бесплатно можем вместо $N$ далее рассматривать $N/p_r^{K_r}$; при этом $p_i$ продолжаем далее по возрастанию, конечно.

 Профиль  
                  
 
 Re: функция и простые числа
Сообщение26.07.2017, 22:01 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group