Невероятно быстрый алгоритм нахождения простых делителей огромных составных чисел

Привет, Хабр!

Хочу представить вам свой очень быстрый алгоритм нахождения простых делителей огромных составных чисел. Однажды на уроке математики мне нужно было найти делители какого‑то числа. Раз уж «лень — двигатель прогресса», я решил поручить эту задачу компьютеру. Но простая программа на 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]). Я же предложил находить только простые, так как их достаточно, чтобы найти любой составной делитель того же числа.

Всем спасибо!