Всем привет есть такая задача ,надо разложить число n на k множителей или вывести Impossible если это не возможно.Не знаю как можно решить .Можете помочь или подсказать алгоритм для решения этой задачи ?
2 ответа
Разлагаем число на простые сомножители - факторизация на этом сайте разбиралась неоднократно. Допустим, это
Если сумма всех l
не меньше k
- то можно :) Как вывести такое разбиение - понятно? Код писать не нужно?
Можете посмотреть ответы на этот вопрос.
-
-
Разлагать число
n
на сомножители. Например,n = 2^2*3^1*5^2 = 300
Так как2+1+2=5
, это число можно разложить до 5 множителей. На 6 и более - нельзя. Например, на 4:300=2*2*3*25
...– Harry15 апр 2017 в 16:23
Чтобы набрать 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>
составным (к примеру, используя Тест Миллера — Рабина).
n
в качестве множителей не допускаются :)