Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

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

RED LIGHT Ученик (90), закрыт 1 год назад
 #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;
}
Лучший ответ
Николай Веселуха Высший разум (356538) 1 год назад
В конце строки 8 поставить точку с запятой.
Остальные ответы
Антон Гараев Мастер (1772) 1 год назад
тебе бы на тостер с такими загадками. а в мейле одни дауничи сидят
RED LIGHTУченик (90) 1 год назад
вы чего
Владимир Алексеев Мудрец (11732) 1 год назад
если хочешь получить ответ, вместо своей проги скажи, что надо сделать
RED LIGHTУченик (90) 1 год назад
ты что глухой.говорю про оптимизацию
Xaker_Two Мыслитель (5038) 1 год назад
ну факториал можно упростить в синтаксисе до
result *= i;

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

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

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

а да и ещё зачем у вас деления в обоих if в decomp? если нет остатка значит одна ветка ИНАЧЕ другая, не надо дважды одно и тоже проверять
RED LIGHTУченик (90) 1 год назад
в оптимизаций такие мелочи не влияют на производительность.
RED LIGHTУченик (90) 1 год назад
и я только один раз вызываю функцию decomp
Сергей Гений (55561) 1 год назад
 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, вроде отрицательных значений не предполагаем а диапазон будет больше.
Похожие вопросы