Comments 7
Ну ok, раз речь про "Невероятно быстрый алгоритм нахождения простых делителей огромных составных чисел", то сколько ваш алгоритм будет факторизовать вот такое не слишком огромное число?
3597284440855924544760705321078319513881289134853978802171066623680480235229732988761104885629809631999005054189544840315407267231713401943322212324974300752954681286642512935564763772827324008300407016109060076912152536812782569409805382513070413043Скрытый текст
Число получено как перемножение вот этих двух чисел из интернета (гугл говорит, что оба простые)
a=5280842695870597262871829916036347793181048105944727626357078127619420046530136938413905659102954019
b=681195151612611689484381505082728530227937846992253495686317828427132018802795367772173239804088945451030304776802491083558288394588076833648046982897
Оказывается, все простые числа, включая то, что мы ищем, имеют вид 6k ± 1, где k — целое число.
Не все числа вида 6k ± 1 простые. Но вы их всё одно тестируете в качестве "простых делителей".
И непонятно, почему вы не используете готовые списки простых чисел из OEIS.
Подход хорош только для числа, состоящего из небольших делителей.
В качестве иллюстрации - ну, сойдёт. Хотя код откровенно попахивает, - и с названиями тут странно, и с побочными эффектами.
Общая идея простая:
перебираем все кандидаты в простые числа: 2, 3, 6k±1 (если там попадутся непростые, то пофиг, мы на их делители уже проверили раньше)
при каждом совпадении делим число, заменяе его на частное от максимальной степени делителя
отсечка - квадрат кандидата-в-делители больше текущего проверяемого числа
Ключевое отличие от наивного алгоритма - там отсечкой было бы "больше исходного числа".
Ну и как это можно переписать красивее (вкусовщина, конечно, но раз уж я критикую стиль, то критикуя-предлагаю)
def gen_prime_candidates():
'''
неограниченный генератор кандидатов в простые числа
'''
# возвращаем первые несколько чисел из известного списка
known = [2, 3] # можно написать хоть до сотни, хоть до тысячи
for p in known:
yield p
# остальные, так и быть, через сито с остатком 6
plast = known[-1] # последнее простое число из списка
k6 = plast//6*6 + 1 # следующее число, кратное 6
while True:
yield k6-1
yield k6+1
k6 += 6
def find_power_and_rest_log(n, dt, t=1):
'''
вспомогательная функция нахождения степени делителя
(за логарифмическое время)
n - делимое
dt = (d**t) - делитель в степени t
t - степень
результат - (p, n')
где n = n' * d**p = n' * (d**t)**u, p = t*u
'''
if n < dt or n % dt != 0:
return 0, n # не делится
# рекурсия позволяет сделать за логарифмическое время
p, n = find_power_and_rest_log(n, dt*dt, t*2)
if n % dt == 0:
p, n = p+t, n//dt
return p, n
# на самом деле, накладные расходы на рекурсию могут оказаться больше,
# чем на тупой линейный забег (для 64-битных целых это, очевидно, не более 64)
def find_power_and_rest_lin(n, d):
'''
вспомогательная функция нахождения степени делителя
(за линейное время)
n - делимое
d - делитель
результат - (p, n')
где n = n' * d**p
'''
p = 0
while n%d == 0:
p, n = p+1, n//d
return (p, n)
find_power_and_rest = find_power_and_rest_log # или ..._lin
def gen_divisors_and_powers(n):
'''
конечный генератор списка пар (делитель, показатель степени)
'''
for d in gen_prime_candidates():
# отсечка по квадрату
if d*d > n:
break
# находим степень делителя
p, n = find_power_and_rest(n, d)
if p != 0:
yield (d, p)
# отдаём последнее
if n > 1:
yield (n, 1)
def show_divisor_and_power(d, p):
return f'{d}' if p==1 else f'{d}^{p}'
def show_divisors_and_powers(n):
'''
формирует строку вида "2^a * 3^b * ..."
'''
# почему не сразу print в цикле,
# потому что пришлось бы реализовывать логику вставки оператора
# перед вторым и последующими элементами
return ' * '.join(
show_divisor_and_power(d,p)
for (d, p) in gen_divisors_and_powers
)
def print_divisors_and_powers(n):
print(n, '=', show_divisors_and_powers(n))
У вас "быстрота" за а счет двух простых оптимизаций:
1) Cокращать делители по мере их нахождения.
Идея хорошая, но очевидная и давно всем известная.
Вот, посмотрите например на код тут, в функцию findDivisors.
Это очень простая идея, она уже была изобретена тысячи раз и даже какого-то названия не имеет. Помнится, я ее применял еще лет 20 назад будучи школьником на какой-то олимпиаде.
2) Перебирать отдельно 2, 3 и потом все числа заведомо не делящиеся на 2 и 3, потому что только такие могут быть простыми. Это тоже очевидная и давно известная оптимизация, называющаяся "методом колеса" или "колесной оптимизацией". Можно взять любой набор простых чисел, перемножить их и потом надо рассматривать в качестве кандидатов на простые числа только те, которые заведомо взаимно просты с этим произведением.
Чаще всего эту идею применяют в решете эратосфена.
В наивном разложении на делители ее используют редко, потому что там алгоритм итак относительно быстрый в своей области применения - до корня. Несколько процентов вы этим колесом еще выдавите, но на маленьких числах (как у вас, влезающих в обычные типы) это смысла это несет мало, а код усложняет заметно. А если уж раскладывать длинные (десятки десятичных цифр) числа, то надо расчехлять тяжелую математику и применять что-то поумнее наивного перебора. Например, какие-нибудь эллиптические кривые.
В целом, алгоритм чуть-чуть быстрее стандартной реализации, но для "огромных" составных чисел не применим и ничего нового не привнес.
Edit: Более того, даже та статья на хабре на которую вы в конце ссылаетесь, сначала находит простые делители применяя первую оптимизацию, а потом строит все делители. Это функция prchoosediv там.
Скорее бегите на mersenne.org - у нас там огромное количество людей напрасно жгут киловатто-тысячелетия именно ради того, чтобы найти делители больших чисел.
Задача разложения числа на простые множители называется факторизацией. Она достаточно хорошо изучена, и существует множество эффективных алгоритмов для её решения. А теперь ещё и невероятно быстрый появился, наконец-то дождались.
Невероятно быстрый алгоритм нахождения простых делителей огромных составных чисел