Как уменьшить время выполнения программы, написанной на С++?

Question

yuharu @yuharu

C++

Как уменьшить время выполнения программы, написанной на С++?

Задача: Какое наименьшее число n можно представить в виде произведения n = a∙b ровно k способами? Произведения a∙b и b∙a считаются одним способом, все числа натуральные (1 ≤ k ≤ 50).
Лимит времени: 1 сек.
При k=50 у меня тратится больше 2 сек.
Программный код:

int factors(int);

int main()
{
    int k;
	cin>>k;
	cout<<factors(k);
	cout<<endl;
	system("pause");
	return 0;
}

int factors(int k)
{
    int n=0, kol;
	while(true)
	{
		kol=0;
		n++;
		for (int i=n; i>0; i--)
			if (n%i==0)
			{
				if (i*i==n)
					kol=kol+2;
				else kol++;
			}
		if (kol/2==k)
			break;
	}
	return n;
}

Вопрос задан более трёх лет назад
2464 просмотра

3 комментария

Подписаться 2 Оценить 3 комментария

GavriKos @GavriKos

Какое жуткое форматирование... Ctrl+k, d в студии сделайте...

Написано более трёх лет назад
Антон Федорян @AnnTHony

Не до конца понятна суть задачи. Например, нужно найти 50 способов (если k=50) представить число 153 (n=153) в виде произведения двух чисел (a*b), правильно я понял? Можно увидеть конкретный результат для какого-нибудь числа?

Написано более трёх лет назад
yuharu @yuharu Автор вопроса

Антон Федорян: например введено число k=3, то есть нужно найти наименьшее число, которое можно составить из 3 произведений чисел, ответом будет 12, т.к. 1*12, 2*6, 3*4

Написано более трёх лет назад

Пригласить эксперта

Ответы на вопрос 2

3 комментария

yuharu @yuharu Автор вопроса

да я как раз и понимаю, что время уходит из за большого кол-ва итераций, и надо их сократить, но я пока не знаю как...

Написано более трёх лет назад
whiteBlackness @whiteBlackness

yuharu: так я и написал как. Не перебирать все числа, а сначала понять, какое должно быть разложение на простые числа (факторизация). А потом просто взять первые несколько простых чисел - тогда будет минимальное число.

Твоё искомое число представляется в a * a * ... * a * b * b * .. * b * c ..
где a, b, c - это различные простые числа.
Например
2 * 2 * 3 * 5 * 5

a a b c c

Данное разложение можно разделить пополам несколькими различными способами
| aabcc
a | aabcc
aa | bcc
ab | abcc
...
и т.д.

Число таких вариантов разделения - это твоё k

Тебе надо найти такие последовательности aabbc, которые дают тебе именно заданное число разделений.

После этого, как у тебя появилось несколько претендентов на разделение
например aabbc и abcd
ты вместо букв подставляешь первые несколько простых чисел - и смотришь какой вариант даст минимальное число.

Чем больше раз буква встречается - тем меньшее простое число должно ей соответствовать.
Но всё равно может быть придётся проверить несколько вариантов.

Написано более трёх лет назад
yuharu @yuharu Автор вопроса

whiteBlackness: спасибо :) попробую

Написано более трёх лет назад

6 комментариев

yuharu @yuharu Автор вопроса

у вас неправильный код, лишь с некоторыми числами проходит, проверьте и убедитесь в этом сами :)

Написано более трёх лет назад
Tlito @tlito

я заметил что не работал с 1, исправил: добавил одну строку в начало функции поверка если к=1. а с какими еще не работает? код и принсткрин новый тут tlito.ru/node/203

Написано более трёх лет назад
yuharu @yuharu Автор вопроса

Tlito: не в 1 дело, со многими числами не проходит, я запустила программу на этом сайте и лишь 38% прошло решение

Написано более трёх лет назад
Tlito @tlito

понятно. если бы я мог так же проверить, может быть я бы узнал как исправить. а так я мог проверить только для 1, 2, 3, 4

Написано более трёх лет назад
yuharu @yuharu Автор вопроса

Tlito: к сожалению проваленные тесты не показываются с какими они были вариантами чисел

Написано более трёх лет назад
Tlito @tlito

тогда я не знаю как сделать этот алгоритм. и не могу вам помочь.
спросите учителя об алгоритме

Написано более трёх лет назад

Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации

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

Python

+4 ещё

Средний
Rust. Как изменить часть файла в zip архиве?
- 1 подписчик
- 7 минут назад
- 14 просмотров
1

ответ
C++

+1 ещё

Простой
Рекурсивный ввод-вывод последовательности без использования массивов и списоков?
- 2 подписчика
- час назад
- 137 просмотров
0

ответов
C++

+2 ещё

Средний
Как сделать маштабирование относительно центра екрана?
- 1 подписчик
- 7 часов назад
- 43 просмотра
0

ответов
C++

Простой
Как составить план по изучению языка C++?
- 1 подписчик
- 21 час назад
- 103 просмотра
2

ответа
C++

+2 ещё

Простой
Как подключить библиотеку TgBot к срр проекту?
- 1 подписчик
- вчера
- 61 просмотр
1

ответ
C++

+2 ещё

Простой
Как выровнять по центру текст подсказки и вводимый текст в QTextEdit?
- 1 подписчик
- вчера
- 33 просмотра
1

ответ
C++

Простой
Как можно разделить данный код (см. ниже) по header'ам и cpp'ам, учитывая зависимости в нём?
- 1 подписчик
- вчера
- 65 просмотров
2

ответа
Windows

+1 ещё

Простой
Как исправить ошибку буфера с UART?
- 1 подписчик
- 15 апр.
- 145 просмотров
2

ответа
C++

Простой
Как вернуть двумерный массив?
- 1 подписчик
- 15 апр.
- 79 просмотров
3

ответа
C++

+1 ещё

Простой
Как реализовать многопоточность на C++?
- 1 подписчик
- 14 апр.
- 129 просмотров
1

ответ
Показать ещё Загружается…

Kotlin Backend-разработчик

vivaCRM • Москва

от 200 000 до 250 000 ₽

Backend разработчик

Unicorn • Санкт-Петербург

До 350 000 ₽

Системный аналитик

ЦИФРА

До 270 000 ₽

Помощь с водпресс

18 апр. 2024, в 21:00

150 руб./за проект

Спарсить ссылки на все товары конкретного продавца в озон

18 апр. 2024, в 20:13

2000 руб./за проект

Устранить проблемы с парсерами и отображением новостей

18 апр. 2024, в 20:08

7000 руб./за проект

Какое жуткое форматирование... Ctrl+k, d в студии сделайте...
Не до конца понятна суть задачи. Например, нужно найти 50 способов (если k=50) представить число 153 (n=153) в виде произведения двух чисел (a*b), правильно я понял? Можно увидеть конкретный результат для какого-нибудь числа?
Антон Федорян: например введено число k=3, то есть нужно найти наименьшее число, которое можно составить из 3 произведений чисел, ответом будет 12, т.к. 1*12, 2*6, 3*4

Answer 1 · 2015-09-30 14:08:48

Самый лучший способ - это алгоритм поменять. У тебя тут тупой перебор.
Гораздо эффективнее зайти с другой стороны задачи.
Любое число факторизуется на произведение простых чисел.
Тебе просто надо понять на сколько простых чисел должно факторизоваться твоё число - и взять столько первых простых чисел.

1 пара у тебя всегда есть. 1 * само число.
Осталось понять какая должна быть струтура факторизации числа (сколько должно быть одинаковых простых чисел и сколько различных).

Answer 2 · 2015-10-01 00:45:05

я написал код, решающий эту задачу, который выполняется максимум за 0.4секунды на интел 2Ггц четырехяденом, ос убунту. в компиляторе code::blocks отображается время.
вы либо на сдк запускаете, либо в учет идет время ожидания ввода. в моей программе ввод я отключил и при к=50 время 0,1...0.4 на картинке видно 0.2
не знаю насколько моя программа оптимальна, но я точно не понял комментарий выше по aa|bccdd... aabcc|dd...

код я разместил на сайте в графе программирование - с++
tlito.ru/node/203

Как уменьшить время выполнения программы, написанной на С++?

Войдите, чтобы написать ответ

Минуточку внимания

Войдите на сайт