@yuharu

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

Задача: Какое наименьшее число 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;
}
  • Вопрос задан
  • 760 просмотров
Пригласить эксперта
Ответы на вопрос 2
  • @whiteBlackness
    Самый лучший способ - это алгоритм поменять. У тебя тут тупой перебор.
    Гораздо эффективнее зайти с другой стороны задачи.
    Любое число факторизуется на произведение простых чисел.
    Тебе просто надо понять на сколько простых чисел должно факторизоваться твоё число - и взять столько первых простых чисел.

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

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

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

Войти через TM ID
Похожие вопросы