Оптимизация кода программы

@Fixer_84 · Регистрация: 30.04.2016

Author24 — интернет-сервис помощи студентам

Здравствуйте, уважаемые форумчане! У меня, как всегда, небольшая проблема с кодом. Парочка тестов не проходят по времени.
Вот условие задачи:

Вывести представление целого числа N в виде произведения простых чисел.

Входные данные:

В первой строке находится единственное число N. 2 <= N <= 2^31 - 1.

Выходные данные:

Выводится список чисел в порядке неубывания, разделённых знаком "*".

Мой код:

C++

#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    int n, q, k;
    cin >> n;
    k = 2;
    while (n >= k * k) {
        if (n % k == 0) {
            n /= k;
            cout << k << "*";
        } else k++;
    }
    cout << n;
}

Помогите, пожалуйста, оптимизировать

Ну а если не получится, то другой алгоритм

@Ромаха · 18.06.2018, 18:51

long long

Добавлено через 1 минуту
Если кинуть большое простое, то можно схватить переполнение, которое приведет к непонятно чему

@SpBerkut · 18.06.2018, 18:53

Ну, как вариант, нужно колдовать над 13-й строкой. Нет нужды перебирать все множители подряд. Достаточно только нечётных, а двойку в начале обрабатывать отдельно.

@Fixer_84 · 18.06.2018, 18:55 **[ТС]**

Ромаха, спасибо! Вы как всегда выручайте меня

Добавлено через 36 секунд

Сообщение от Ромаха

Если кинуть большое простое, то можно схватить переполнение, которое приведет к непонятно чему

Спасибо! Теперь все получилось.

@Fixer_84 · 19.06.2018, 20:46 **[ТС]**

Ромаха, а так срабатывает без long long:

C++

#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    int n, q, k;
    cin >> n;
    k = 2;
    while (k <= sqrt(n)) {
        if (n % k == 0) {
            n /= k;
            cout << k << "*";
        } else k++;
    }
    cout << n;
}

Тут точно дело в этом было:

C++

1	while (n >= k * k) {...}

@Ромаха · 19.06.2018, 21:15

Сообщение от Ромаха

можно схватить переполнение

Переполнение. Будет когда? Молодца. При умножении

Новые блоги и статьи
[golang] 80. Remove Duplicates from Sorted Array II alhaos 28.01.2025 В предоставленном упорядоченном по возрастанию целочисленном слайсе, оставить уникальные элементы полюс один возможный дубликат. Вернуть количество таких элементов. / / . . .	Что такое внедрение зависимостей и для чего оно применяется bytestream 27.01.2025 В современной разработке программного обеспечения одной из ключевых проблем является управление зависимостями между различными компонентами системы. Внедрение зависимостей (Dependency Injection, DI). . .	Как установить cellpadding и cellspacing в CSS bytestream 27.01.2025 При создании веб-страниц с табличными данными разработчики часто сталкиваются с необходимостью правильного оформления внутренних и внешних отступов в таблицах. В традиционной разметке HTML для этих. . .	Чем отличаются public, protected, package-private и private в Java bytestream 27.01.2025 В языке программирования Java механизм модификаторов доступа играет ключевую роль в реализации одного из фундаментальных принципов объектно-ориентированного программирования - инкапсуляции. . . .	Зачем нужно explicit в C++. Преобразование типов bytestream 27.01.2025 В мире программирования на C++ управление преобразованием типов данных играет crucial роль в создании надежного и безопасного кода. Язык C++ предоставляет множество механизмов для контроля над. . .	Как создать удалённую (remote) ветку в Git bytestream 27.01.2025 Система контроля версий Git стала неотъемлемой частью современной разработки программного обеспечения, предоставляя разработчикам мощные инструменты для управления кодовой базой. Одним из ключевых. . .
Как создать утечку памяти в Java bytestream 27.01.2025 Утечка памяти в Java представляет собой ситуацию, когда программа неэффективно использует доступную память, удерживая ссылки на объекты, которые больше не нужны для работы приложения. Несмотря на. . .	КуМир: как решать задачи на числа bytestream 27.01.2025 КуМир (Комплект Учебных МИРов) представляет собой уникальную образовательную среду программирования, разработанную специально для обучения основам алгоритмизации и программирования. Эта система. . .	Исполнитель Черепаха в КуМир: как решать задачи bytestream 27.01.2025 Исполнитель Черепаха в системе КуМир представляет собой мощный образовательный инструмент, который помогает освоить основы программирования через визуальное представление результатов выполнения. . .	КуМир: как решать задачи на массивы bytestream 27.01.2025 Массивы представляют собой важнейшую структуру данных в программировании, и система КуМир предоставляет удобные инструменты для работы с ними. В контексте КуМир массив можно представить как. . .	[golang] 26. Remove Duplicates from Sorted Array alhaos 27.01.2025 Необходимо удалить дубликаты из предоставленного целочисленного отсортированного по взрастанию слайса, нужно изменить значения в слайсе и вернуть количество элементов. / / . . .	КуМир, исполнитель Робот. Решение задач bytestream 27.01.2025 КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения программированию, которая была создана в Отделении информатики Российской Академии наук. Эта система разработана. . .

@Ромаха 353 / 134 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	18.06.2018, 18:51	2
	long long Добавлено через 1 минуту Если кинуть большое простое, то можно схватить переполнение, которое приведет к непонятно чему 1

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,274
	18.06.2018, 18:53	3
	Ну, как вариант, нужно колдовать над 13-й строкой. Нет нужды перебирать все множители подряд. Достаточно только нечётных, а двойку в начале обрабатывать отдельно. 1

@Fixer_84 1505 / 968 / 812 Регистрация: 30.04.2016 Сообщений: 3,334
	18.06.2018, 18:55 [ТС]	4
	Ромаха, спасибо! Вы как всегда выручайте меня Добавлено через 36 секунд Сообщение от Ромаха Если кинуть большое простое, то можно схватить переполнение, которое приведет к непонятно чему Спасибо! Теперь все получилось. 0

@Ромаха 353 / 134 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	19.06.2018, 21:15	6
	Сообщение от Ромаха можно схватить переполнение Переполнение. Будет когда? Молодца. При умножении 0

Опции темы