Привет, Хабр!
Хочу представить вам свой очень быстрый алгоритм нахождения простых делителей огромных составных чисел. Однажды на уроке математики мне нужно было найти делители какого‑то числа. Раз уж «лень — двигатель прогресса», я решил поручить эту задачу компьютеру. Но простая программа на Python по перебору до корня мне показалась скучной, и тогда я решил найти более интересный способ.
Есть идеи?
Всем известно, что чтобы найти абсолютно все делители какого‑либо числа, нужно перебрать всё вплоть до его корня. Но кто сказал, что мы должны это делать, когда наше число — составное? Что‑ж, давайте посмотрим на примере.
Допустим, нам дано число 715. Мы начинаем перебирать: 2, 3, 4, 5 — и 715 делится на 5 без остатка. Простая программа продолжила бы так до 26 (так как √715 ≈ 26). Но если взять и поделить наше число на найденный делитель, то получим 715 ÷ 5 = 143. А теперь вспомним, что число есть произведение всех своих простых делителей (учитывая их степени), то есть 715 = 5 × дел_N2 × дел_N3 = 5 × 143. Следовательно, 5 × дел_N2 × дел_N3 = 5 × 143. Вопрос: зачем теперь искать делители числа 715, если мы можем найти делители числа 143? Поехали! Отныне наша программа перебирает не до 26, а до 11 (так как √143 ≈ 11). Перебором доходим до 11 и понимаем, что 143 делится на 11. Повторяем действия: 143 ÷ 11 = 13, а значит теперь перебираем до 3 (так как √13 + 1 ≈ 3). Но мы остановились на 11 (11 > 3), а это значит, что мы уже перебрали все числа до √13, и следовательно 13 — простое. Итак, 5 × 11 × 13 = 715. Круто!
Ускорение!
Итак, мы нашли все простые делители числа 715 перебрав все числа от 2 не до 27, а до 11. Таким образом, мы перебрали 10 чисел (от 2 до 11). Можно ли сократить перебор?
Можно! Оказывается, все простые числа, включая то, что мы ищем, имеют вид 6k ± 1, где k — целое число. В начале мы проверяем делимость на 2 и на 3. Затем мы можем находить простые числа, перебирая k. Так как теперь мы перебираем не каждое число, а только те, которые имеют вид 6k ± 1, то мы работаем в 3 раза быстрее (перепрыгиваем шесть чисел, проверяем два). Неплохо!
Рабочий код
Ладно, пора написать код. Так и быть, я буду использовать Python, хотя предпочитаю Rust (библиотека есть на Github и Crates.io).
# Если делитель встречается несколько раз def get_power(number: int, divisor: int) -> int: power = 0 while number % divisor == 0: number //= divisor power += 1 else: print(f" ^{power}") return number def get_divisors(number: int): # Если число меньше 2 - ошибка if number < 2: print("Error") return # Если число 2 или 3, возвращаем само число (хотя эта проверка необязательна) if number < 4: print(f"{number} ^1") return # Проверяем делимость на 2 if number % 2 == 0: print(2, end = "") number = get_power(number, 2) # Проверяем делимость на 3 if number % 3 == 0: print(3, end = "") number = get_power(number, 3) # Цикл перебора по формуле 6k ± 1 divisor = 5 while divisor * divisor < number + 1: if number % divisor == 0: print(divisor, end = "") number = get_power(number, divisor) if number % (divisor + 2) == 0: print(divisor + 2, end = "") number = get_power(number, divisor + 2) divisor += 6 # Если в конце число не рано 1 - то это последний простой множитель if number != 1: print(f"{number} ^1")
Здесь реализовано все, о чем я писал. Также не забываем прописать функцию get_power, так как делитель может встречаться несколько раз.
Вывод
Изучив наш любимый Хабр, я наткнулся на статью тоже про быстрые способы нахождения делителей чисел. Но все программы почему‑то ищут абсолютно все делители, даже составные (например 12: [2, 3, 4, 6], хотя можно обойтись [2^2, 3^2]). Я же предложил находить только простые, так как их достаточно, чтобы найти любой составной делитель того же числа.
Всем спасибо!
Комментарии (9)
Akina
05.08.2026 11:30Оказывается, все простые числа, включая то, что мы ищем, имеют вид 6k ± 1, где k — целое число.
Не все числа вида 6k ± 1 простые. Но вы их всё одно тестируете в качестве "простых делителей".
И непонятно, почему вы не используете готовые списки простых чисел из OEIS.
nickolaym
05.08.2026 11:30В качестве иллюстрации - ну, сойдёт. Хотя код откровенно попахивает, - и с названиями тут странно, и с побочными эффектами.
Общая идея простая:
перебираем все кандидаты в простые числа: 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))
wataru
05.08.2026 11:30У вас "быстрота" за а счет двух простых оптимизаций:
1) Cокращать делители по мере их нахождения.Идея хорошая, но очевидная и давно всем известная.
Вот, посмотрите например на код тут, в функцию findDivisors.
Это очень простая идея, она уже была изобретена тысячи раз и даже какого-то названия не имеет. Помнится, я ее применял еще лет 20 назад будучи школьником на какой-то олимпиаде.
2) Перебирать отдельно 2, 3 и потом все числа заведомо не делящиеся на 2 и 3, потому что только такие могут быть простыми. Это тоже очевидная и давно известная оптимизация, называющаяся "методом колеса" или "колесной оптимизацией". Можно взять любой набор простых чисел, перемножить их и потом надо рассматривать в качестве кандидатов на простые числа только те, которые заведомо взаимно просты с этим произведением.
Чаще всего эту идею применяют в решете эратосфена.
В наивном разложении на делители ее используют редко, потому что там алгоритм итак относительно быстрый в своей области применения - до корня. Несколько процентов вы этим колесом еще выдавите, но на маленьких числах (как у вас, влезающих в обычные типы) это смысла это несет мало, а код усложняет заметно. А если уж раскладывать длинные (десятки десятичных цифр) числа, то надо расчехлять тяжелую математику и применять что-то поумнее наивного перебора. Например, какие-нибудь эллиптические кривые.
В целом, алгоритм чуть-чуть быстрее стандартной реализации, но для "огромных" составных чисел не применим и ничего нового не привнес.
Edit: Более того, даже та статья на хабре на которую вы в конце ссылаетесь, сначала находит простые делители применяя первую оптимизацию, а потом строит все делители. Это функция
prchoosedivтам.
ky0
05.08.2026 11:30Скорее бегите на mersenne.org - у нас там огромное количество людей напрасно жгут киловатто-тысячелетия именно ради того, чтобы найти делители больших чисел.
axion-1
05.08.2026 11:30Задача разложения числа на простые множители называется факторизацией. Она достаточно хорошо изучена, и существует множество эффективных алгоритмов для её решения. А теперь ещё и невероятно быстрый появился, наконец-то дождались.
Bardakan
05.08.2026 11:30Заголовок:
Невероятно быстрый алгоритм нахождения простых делителей огромных составных чисел
но при этом автор берет сравнительно маленькое число, да еще и удобное для себя - 715 и пытается на этом вывести какой-то продвинутый алгоритм на одном единственном частном случае.
А что вы скажете, если у вас число например 23х23 = 529, Т.е. придется проверять вообще все простые множители до 26 (т.е. до 23 включительно)?
Итак, мы нашли все простые делители числа 715 перебрав все числа от 2 не до 27, а до 11. Таким образом, мы перебрали 10 чисел (от 2 до 11). Можно ли сократить перебор?
Самый оптимальный алгоритм - заранее составить список простых чисел. Для этого достаточно последовательно "вычеркивать" числа в массиве - операция с линейной сложностью. Вы скорее всего проиграете по памяти, но выиграете по быстродействии. Какой смысл в том, что вы пытаетесь сократить перебор? Чем больше числа, тем больше вероятности, что ваше число "6k ± 1" окажется составным, и проверять его нет смысла. А арифметические операции считаются дешевле, чем операции проверки.
Рекомендую автору статьи почитать про "сложность алгоритмов".
fish224
05.08.2026 11:30Перебор простых множителей, даже оптимизированный как у Вас - все равно крайне медленный по сравнению с современными продвинутыми методами. Alpertron позволяет разложить 80-значное число за несколько минут, при этом выполняясь прямо в браузере пользователя. А Ваш метод, даже на самом мощном компьютере, никогда бы не смог дойти до перебора 40-значных простых множителей и за миллионы лет.
tenzink
Ну ok, раз речь про "Невероятно быстрый алгоритм нахождения простых делителей огромных составных чисел", то сколько ваш алгоритм будет факторизовать вот такое не слишком огромное число?
Скрытый текст
Число получено как перемножение вот этих двух чисел из интернета (гугл говорит, что оба простые)