โปรแกรม C++ ตรวจสอบว่า n เขียนเป็นผลคูณของ k ตัวเลขได้หรือไม่

สมมติเรามีตัวเลข N อีกตัวเลขหนึ่งคือ k เราต้องตรวจสอบว่าตัวเลขสามารถแทนได้ด้วย k ตัวเลขหรือไม่ สมมติตัวเลข 54 และ k = 3 จะพิมพ์ตัวเลข مثل [2, 3, 9] ถ้าแทนไม่ได้ จะพิมพ์ว่าไม่ได้

เพื่อแก้ปัญหานี้ เราจะหาตัวประกอบเฉพาะทั้งหมดของ N และเก็บในเวกเตอร์ แล้วเพื่อหา k ตัวเลขที่มากกว่า 1 เราตรวจสอบขนาดของเวกเตอร์ว่ามากกว่า k หรือไม่ ถ้าขนาดน้อยกว่า k คืนค่า -1 มิฉะนั้นพิมพ์ตัวประกอบ k-1 ตัวแรก และตัวสุดท้ายจะเป็นผลคูณของตัวเลขที่เหลือทั้งหมด

ตัวอย่าง

#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; // ลด n โดยการหารด้วย 2 
    } 
    for(i = 3; i <= sqrt(n); i = i + 2){ // 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); 
}

ผลลัพธ์

2, 3, 9