Как уменьшить время выполнения программы, написанной на С++?
Самый лучший способ - это алгоритм поменять. У тебя тут тупой перебор.
Гораздо эффективнее зайти с другой стороны задачи.
Любое число факторизуется на произведение простых чисел.
Тебе просто надо понять на сколько простых чисел должно факторизоваться твоё число - и взять столько первых простых чисел.
1 пара у тебя всегда есть. 1 * само число.
Осталось понять какая должна быть струтура факторизации числа (сколько должно быть одинаковых простых чисел и сколько различных).
я написал код, решающий эту задачу, который выполняется максимум за 0.4секунды на интел 2Ггц четырехяденом, ос убунту. в компиляторе  code::blocks отображается время.
вы либо на сдк запускаете, либо в учет идет время ожидания ввода. в моей программе ввод я отключил и при к=50 время 0,1...0.4 на картинке видно 0.2
не знаю насколько моя программа оптимальна, но я точно не понял комментарий выше по aa|bccdd... aabcc|dd...
код я разместил на сайте в графе программирование - с++
tlito.ru/node/203