Разложить число n на k множителей

Разлагаем число на простые сомножители - факторизация на этом сайте разбиралась неоднократно. Допустим, это

Если сумма всех l не меньше k - то можно :) Как вывести такое разбиение - понятно? Код писать не нужно?

Можете посмотреть ответы на этот вопрос.

Чтобы набрать k множителей, можно начать с 2 и увеличивать по одному пока все простые множители не закончатся или пока k множителей не наберётся, добавляя оставшийся множитель в конце (предполагая, что множители не могут быть равны n или 1 иначе ответ для любого k > 0 был бы: n и k-1 единиц -- исключая тривиальный случай, когда k == 1 и n является множителем себя):

#include <vector>
template<class U>
std::vector<U> k_factors(U n, U k)
{
  std::vector<U> factors;
  if (k == 1) {
    factors.push_back(n);
    return factors;
  }
  else if (k > 1) {
    for (U f = 2; f*f <= n; ++f) {
      while (n % f == 0) { // found prime factor
        factors.push_back(f);
        n /= f;
        if (--k == 1 && n > 1) {
          factors.push_back(n);
          return factors; // found solution
        }
      }
    }
  }
  throw std::invalid_argument("Impossible");
}

Пример:

#include <cstdlib>      // exit
#include <iostream>
#include <string>       // stoul
int main(int argc, char* argv[])
{
  if (argc != 3) {
    std::cerr << "Usage: k-factors <n> <k>\n";
    std::exit(2);
  }
  try {
    auto n = std::stoul(argv[1]), k = std::stoul(argv[2]);
    for (auto f : k_factors(n, k)) std::cout << f << ' ';
    std::cout << std::endl;
  } catch(const std::exception& e) {
    std::cerr << e.what() << '\n';
    std::exit(1);
  }
}

Результат:

$ g++ -std=c++11 *.cc -o k-factors && ./k-factors 18446744073709551615 5
3 5 17 257 281479271743489 

В этом случае даже простое деление в лоб достаточно быстро работает. Хотя ./k-factors 18446744073709551557 2 может занять какое-то время ;) В этом случае полезно проверить является ли n или n/<small prime> составным (к примеру, используя Тест Миллера — Рабина).