Здравствуйте, Mace, Вы писали:

M> С отсеканием лишних вариантов должно работать очень быстро.

Немного подумал и забираю свои слова назад =) Самый быстрый алгоритм, который приходит в голову — O(N^(1+1/3)), но он требует N байтов памяти. N — максимальное возможное значение числа, которое нужно разложить.