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
9638
Цюрих
mathworld говорит, что уже проверка $K > 1$ может оказаться не проще факторизации.

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


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

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


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

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


11/03/08
10215
Москва
Зависит, конечно, от того, какие числа, может, 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
10215
Москва
Уменьшать автоматически - нет, но проверить делимость на $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
10215
Москва
Так не обязательно делить на рекорд. При любой проверке делить и хранить частное.

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

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



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

Сейчас этот форум просматривают: choocha


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

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