3

Написал алгоритм который разложить число на простые множители, работает хорошо, но медленно. Не засчитывает 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;
}
3
  • 1
    Разложение тоже делается за корень: если у числа есть какое-то простое P в разложении, которое больше, чем sqrt(N), то оно ровно одно, так как иначе произведение двух таких уже больше N. Таким образом, обычно пишется цикл от двух до sqrt(N) (включительно) и для каждого числа считается, сколько раз на него можно разделить N. Если после цикла N не равен 1, то это получившееся N - простое, входящее в разложение.
    – EzikBro
    Commented 13 дек. 2020 в 20:20
  • 2
    И соответственно простейший тест, ломающий вашу программу - это любое большое удвоенное простое, например 2 * (10 ^ 9 + 7)
    – EzikBro
    Commented 13 дек. 2020 в 20:22
  • 2
    Посмотрите ru.stackoverflow.com/q/595966/195342
    – Harry
    Commented 13 дек. 2020 в 20:36

2 ответа 2

1

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

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

Цикл делает не более 23170 итераций - (√231 - 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
0

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

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

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

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

1
  • @StanislavVolodarskiy и правда. Из-за этого и сложность алгоритма стала в разы хуже. Commented 7 сент. 2023 в 11:25

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.