Cho số N và số k. Kiểm tra N có thể biểu diễn thành tích của k số không. Ví dụ 54, k=3 → [2,3,9]. Nếu không thể thì in thông báo.
Giải pháp: tìm tất cả thừa số nguyên tố của N, lưu vào vector. Để tìm k số > 1, kiểm tra kích thước vector >= k. Nếu nhỏ hơn thì trả -1, ngược lại in k-1 thừa số đầu và thừa số cuối là tích các thừa số còn lại.
Ví dụ mã nguồn
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int getKFactors(int n, int k) {
int i;
vector<int> vec;
while (n % 2 == 0) {
vec.push_back(2);
n = n / 2;
}
for (i = 3; i <= sqrt(n); i += 2) {
while (n % i == 0) {
n = n / i;
vec.push_back(i);
}
}
if (n > 2)
vec.push_back(n);
if (vec.size() < k) {
cout << "Cannot be represented";
return -1;
}
for (int i = 0; i < k-1; i++)
cout << vec[i] << ", ";
int prod = 1;
for (int i = k-1; i < vec.size(); i++)
prod = prod * vec[i];
cout << prod << endl;
}
int main() {
int n = 54, k = 3;
getKFactors(n, k);
}
Kết quả đầu ra
2, 3, 9