Ускорить алгоритм разложения числа на простые множители

Question

Написал алгоритм который разложить число на простые множители, работает хорошо, но медленно. Не засчитывает 2 теста, исчерпан лимит времени. Входное число, которое нужно разложить в пределах от 1 до 2 (на 31 степени) -1. Учёл ввод простого числа, так что это не должно мешать, да и не в нём дело, те 2 теста, которые не проходят по времени не предоставляют простое число, проверял выводом n-1 для любого случая. Как можно ускорить это ?

#include <iostream>
#include <cmath>

using namespace std;

int rozout(long long n);
bool prime(long long n);

int main() {
    long long n;
    cin >> n;
    if (prime(n))
    {
        cout << n;
        return 0;
    }
    rozout(n);
}

int rozout(long long n)
{
    long long i = 2;
    while (n > 1)
    {
        while (n % i == 0)
        {
            cout << i;
            if (n != i) cout << "*";
            n /= i;
        }
        if (i <= 2) i++;
        else i += 2;
    }
    return 1;
}

bool prime(long long n)
{
    long double S = sqrt(n);
    for (long long i = 2; i <= S; i++)
    {
        if (n % i == 0)
        {
            return false;
            break;
        }
    }
    return true;
}

Answer 1

Вот пример реализации факторизации числа:

void rozout(long long n) {
int j = 2;
while ((long long)j * j <= n) {
    if (n % j == 0) {
        cout << j << " * ";
        n /= j;
        j = 2;
    }
    else ++j;
}
cout << n << endl;
}

Я думаю для чисел от [2, 2^31 - 1] он достаточно быстрый.

И думаю нет смысла делать сначала проверку на простоту, потому что алгоритм выше выведет простое число за тоже время, что и проверка этого числа на простоту, зато не придется тратить время на проверку простоты составного числа.

Answer 2

Быстрое элементарное разложение. Если число - ноль или один, печатаем его. Иначе выделяем из числа двойки - делим на два пока делится. Затем перебираем нечётные числа начиная с трёх и проверяем делимость. Если делится, то делим пока делится. Можно показать, что хотя перебираются все нечётные числа, на печать попадут только простые. Поиск завершается когда возможный делитель добрался до √n. Дальше искать нет смысла: если n разлагается в произведение, один из множителей должен быть не больше корня. После цикла добавляем в разложение n, если оно ещё больше единицы.

Если в цикле найден делитель, n уменьшается и обновляется значение √n. Корень считается через std::sqrt(double). Для n < 2³¹ вычисления будут точными.

Цикл делает не более 23170 итераций - (√2³¹ - 1) / 2. В каждой итерации делается одно сравнение (i <= n_sqrt), одно деление со сравнением (n % i == 0), один инкремент (i += 2).

Худшие по времени случаи для программы: простые числа, квадраты простых чисел, произведения двух близких простых чисел.

#include <cmath>
#include <iostream>

uint32_t isqrt(uint32_t n) {
    return static_cast<uint32_t>(std::sqrt(static_cast<double>(n)));
}

void print_factorization(uint32_t n) {
    bool first = true;
    auto print = [&first](uint32_t factor) {
        if (!first) {
            std::cout << '*';
        }
        std::cout << factor;
        first = false;
    };

    if (n <= 1) {
        print(n);
    } else {
        for (; n % 2 == 0; n /= 2) {
            print(2);
        }

        uint32_t i = 3;
        uint32_t n_sqrt = isqrt(n);

        while (i <= n_sqrt) {
            if (n % i == 0) {
                do {
                    print(i);
                    n /= i;
                } while (n % i == 0);
                n_sqrt = isqrt(n);
            }
            i += 2;
        }

        if (n > 1) {
            print(n);
        }
    }
    std::cout << '\n';
}

int main() {
    uint32_t n;
    std::cin >> n;
    print_factorization(n);
}

$ time echo 2146654199 | ./a.out
46327*46337

real  0m0.002s
user  0m0.004s
sys   0m0.000s

БЛОГ НА HUSL

Ускорить алгоритм разложения числа на простые множители

Ответы (2 шт):