C/C++

Как оптимизировать этот код

 #include     

#include 

#include 



std::vector prime_numbers;



void set_prime_numbers() {

    prime_numbers.reserve(110)

    prime_numbers.push_back(2);

    prime_numbers.push_back(3);

    for (int i = 1; i < 102; i++) {

        prime_numbers.push_back(6 * i - 1);

        prime_numbers.push_back(6 * i + 1);

    }

}



long long fact(int n) {

    long long result = 1;

    for (int i = n; i > 0; i--) {

        result = result * i;

    }

    return result;

}



std::string decomp(long long n) {

    set_prime_numbers();

    n = fact(n);

    std::string result;

    int d = 1;

    for (int elem = 0;;) {

        if (n == 1){

            result += std::to_string(prime_numbers[elem]);

            break;

        }

        

        if (n % prime_numbers[elem] == 0) {

            n = n / prime_numbers[elem];

            d++;

        }

        if (n % prime_numbers[elem] != 0) {

            result += std::to_string(prime_numbers[elem]) + ((d==1)?"":"^" + std::to_string(d)) + " * ";

            ++elem;

            n = n / prime_numbers[elem];

            d = 1;

        }

    }

    return result;

}
Ермек Аралбаев
Ермек Аралбаев
90
В конце строки 8 поставить точку с запятой.
Михаил Циммер
Михаил Циммер
86 033
Лучший ответ 
 std::string decomp(long long n) {

 

    if (prime_numbers.empty()) set_prime_numbers(); // запускает формирование прайм_нум если он пуст

 

    n = fact(n);

 

    std::string result;

 

    int d = 0; //у нас все таки может быть нулевая степень ну чисто в теории))

 

    int prime_num = 0;

 

    do //пока множетель числа не равен 1

 

    {

 

        while (n % prime_numbers[prime_num]==0)

 

        {

 

            n /= prime_numbers[prime_num];

 

            d++;

 

        }

 

        // теперь проверка на неравенство не нужна, сразу формируем множетели

 

            result += std::to_string(prime_numbers[prime_num]) + ((d == 1) ? "" : "^" + std::to_string(d));

 

            //сбрасываем степень

 

            d = 0;

 

            //переходим к следующему числу

 

        ++prime_num;

 

        //добавляем * если это не последний множетель

 

        if(n!=1) result += " * ";

 

    } while (n != 1);

 

    return result;

}
Ваша программа не работала должным образом, поэтому нуждалась не в оптимизации а в исправлении.
Ну и по мелочам - можно бы добавить проверку на переполнение LL а то факториалы сильно быстро растут
ах да, вместо LL инт лучше использовать unsigned LL или size_t, вроде отрицательных значений не предполагаем а диапазон будет больше.
Иван Бондаренко
Иван Бондаренко
51 416
если хочешь получить ответ, вместо своей проги скажи, что надо сделать
Геннадий Логвиненко
Геннадий Логвиненко
11 711
Ермек Аралбаев ты что глухой.говорю про оптимизацию
ну факториал можно упростить в синтаксисе до
result *= i;

или до макаронины вида
for (int i = n; i > 0; result *= i--);

далее у вас не совсем правильный prime - 25 является простым? (i == 4)
еслиб все было так легко - не былоб так трудно их считать

но вообще праймы то как раз и можно опустить и расчитывать их надо один раз, а не при каждом вызове decomp (ile или ress?). просто создайте где-то функцию-инициализатор массива праймов со 110 макаронинами и вызовите её один раз допустим в main или как-то ещё если не надо всегда но надо при использовании хотябы раз

а да и ещё зачем у вас деления в обоих if в decomp? если нет остатка значит одна ветка ИНАЧЕ другая, не надо дважды одно и тоже проверять
Васин Станислав
Васин Станислав
5 038
Ермек Аралбаев в оптимизаций такие мелочи не влияют на производительность.
Ермек Аралбаев и я только один раз вызываю функцию decomp
тебе бы на тостер с такими загадками. а в мейле одни дауничи сидят
ЮО
Юрий Орлов
1 771

Похожие вопросы