# Find if n can be written as product of k numbers

Given a positive number n, we need to print exactly k positive numbers (all greater than 1) such that product of those k numbers is n. If there doesn’t exist such k numbers, print -1 . If there are many possible answer you have to print one of that answer where k numbers are sorted. **Examples:**

Input : n = 54, k = 3 Output : 2, 3, 9 Note that 2, 3 and 9 are k numbers with product equals to n. Input : n = 54, k = 8 Output : -1

This problem uses idea very similar to print all prime factors of a given number.

The idea is very simple. First we calculate all prime factors of n and store them in a vector. Note we store each prime number as many times as it appears in it’s prime factorization. Now to find k numbers greater than 1, we check if size of our vector is greater then or equal to k or not.

- If size is less than k we print -1.
- Else we print first k-1 factors as it is from vector and last factor is product of all the remaining elements of vector.

Note we inserted all the prime factors in sorted manner hence all our number in vector are sorted. This also satisfy our sorted condition for k numbers.

## C++

`// C++ program to find if it is possible to` `// write a number n as product of exactly k` `// positive numbers greater than 1.` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Prints k factors of n if n can be written` `// as multiple of k numbers. Else prints -1.` `void` `kFactors(` `int` `n, ` `int` `k)` `{` ` ` `// A vector to store all prime factors of n` ` ` `vector<` `int` `> P;` ` ` `// Insert all 2's in vector` ` ` `while` `(n%2 == 0)` ` ` `{` ` ` `P.push_back(2);` ` ` `n /= 2;` ` ` `}` ` ` `// n must be odd at this point` ` ` `// So we skip one element (i = i + 2)` ` ` `for` `(` `int` `i=3; i*i<=n; i=i+2)` ` ` `{` ` ` `while` `(n%i == 0)` ` ` `{` ` ` `n = n/i;` ` ` `P.push_back(i);` ` ` `}` ` ` `}` ` ` `// This is to handle when n > 2 and` ` ` `// n is prime` ` ` `if` `(n > 2)` ` ` `P.push_back(n);` ` ` `// If size(P) < k, k factors are not possible` ` ` `if` `(P.size() < k)` ` ` `{` ` ` `cout << ` `"-1"` `<< endl;` ` ` `return` `;` ` ` `}` ` ` `// printing first k-1 factors` ` ` `for` `(` `int` `i=0; i<k-1; i++)` ` ` `cout << P[i] << ` `", "` `;` ` ` `// calculating and printing product of rest` ` ` `// of numbers` ` ` `int` `product = 1;` ` ` `for` `(` `int` `i=k-1; i<P.size(); i++)` ` ` `product = product*P[i];` ` ` `cout << product << endl;` `}` `// Driver program to test above function` `int` `main()` `{` ` ` `int` `n = 54, k = 3;` ` ` `kFactors(n, k);` ` ` `return` `0;` `}` |

## Java

`// Java program to find if it is possible to` `// write a number n as product of exactly k` `// positive numbers greater than 1.` `import` `java.util.*;` `class` `GFG` `{` ` ` `// Prints k factors of n if n can be written` `// as multiple of k numbers. Else prints -1.` `static` `void` `kFactors(` `int` `n, ` `int` `k)` `{` ` ` `// A vector to store all prime factors of n` ` ` `ArrayList<Integer> P = ` `new` `ArrayList<Integer>();` ` ` `// Insert all 2's in list` ` ` `while` `(n % ` `2` `== ` `0` `)` ` ` `{` ` ` `P.add(` `2` `);` ` ` `n /= ` `2` `;` ` ` `}` ` ` `// n must be odd at this point` ` ` `// So we skip one element (i = i + 2)` ` ` `for` `(` `int` `i = ` `3` `; i * i <= n; i = i + ` `2` `)` ` ` `{` ` ` `while` `(n % i == ` `0` `)` ` ` `{` ` ` `n = n / i;` ` ` `P.add(i);` ` ` `}` ` ` `}` ` ` `// This is to handle when n > 2 and` ` ` `// n is prime` ` ` `if` `(n > ` `2` `)` ` ` `P.add(n);` ` ` `// If size(P) < k, k factors are` ` ` `// not possible` ` ` `if` `(P.size() < k)` ` ` `{` ` ` `System.out.println(` `"-1"` `);` ` ` `return` `;` ` ` `}` ` ` `// printing first k-1 factors` ` ` `for` `(` `int` `i = ` `0` `; i < k - ` `1` `; i++)` ` ` `System.out.print(P.get(i) + ` `", "` `);` ` ` `// calculating and printing product` ` ` `// of rest of numbers` ` ` `int` `product = ` `1` `;` ` ` `for` `(` `int` `i = k - ` `1` `; i < P.size(); i++)` ` ` `product = product * P.get(i);` ` ` `System.out.println(product);` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `n = ` `54` `, k = ` `3` `;` ` ` `kFactors(n, k);` `}` `}` `// This code is contributed` `// by chandan_jnu` |

## Python3

`# Python3 program to find if it is possible` `# to write a number n as product of exactly k` `# positive numbers greater than 1.` `import` `math as mt` `# Prints k factors of n if n can be written` `# as multiple of k numbers. Else prints -1` `def` `kFactors(n, k):` ` ` ` ` `# list to store all prime factors of n` ` ` `a ` `=` `list` `()` ` ` ` ` `#insert all 2's in list` ` ` `while` `n ` `%` `2` `=` `=` `0` `:` ` ` `a.append(` `2` `)` ` ` `n ` `=` `n ` `/` `/` `2` ` ` ` ` `# n must be odd at this point` ` ` `# so we skip one element(i=i+2)` ` ` `for` `i ` `in` `range` `(` `3` `, mt.ceil(mt.sqrt(n)), ` `2` `):` ` ` `while` `n ` `%` `i ` `=` `=` `0` `:` ` ` `n ` `=` `n ` `/` `i;` ` ` `a.append(i)` ` ` ` ` `# This is to handle when n>2 and` ` ` `# n is prime` ` ` `if` `n > ` `2` `:` ` ` `a.append(n)` ` ` ` ` `# if size(a)<k,k factors are not possible` ` ` `if` `len` `(a) < k:` ` ` `print` `(` `"-1"` `)` ` ` `return` ` ` ` ` `# printing first k-1 factors` ` ` `for` `i ` `in` `range` `(k ` `-` `1` `):` ` ` `print` `(a[i], end ` `=` `", "` `)` ` ` ` ` `# calculating and printing product` ` ` `# of rest of numbers` ` ` `product ` `=` `1` ` ` ` ` `for` `i ` `in` `range` `(k ` `-` `1` `, ` `len` `(a)):` ` ` `product ` `*` `=` `a[i]` ` ` `print` `(product)` `# Driver code` `n, k ` `=` `54` `, ` `3` `kFactors(n, k)` `# This code is contributed` `# by mohit kumar 29` |

## C#

`// C# program to find if it is possible to` `// write a number n as product of exactly k` `// positive numbers greater than 1.` `using` `System;` `using` `System.Collections;` `class` `GFG` `{` ` ` `// Prints k factors of n if n can be written` `// as multiple of k numbers. Else prints -1.` `static` `void` `kFactors(` `int` `n, ` `int` `k)` `{` ` ` `// A vector to store all prime factors of n` ` ` `ArrayList P = ` `new` `ArrayList();` ` ` `// Insert all 2's in list` ` ` `while` `(n % 2 == 0)` ` ` `{` ` ` `P.Add(2);` ` ` `n /= 2;` ` ` `}` ` ` `// n must be odd at this point` ` ` `// So we skip one element (i = i + 2)` ` ` `for` `(` `int` `i = 3; i * i <= n; i = i + 2)` ` ` `{` ` ` `while` `(n % i == 0)` ` ` `{` ` ` `n = n / i;` ` ` `P.Add(i);` ` ` `}` ` ` `}` ` ` `// This is to handle when n > 2 and` ` ` `// n is prime` ` ` `if` `(n > 2)` ` ` `P.Add(n);` ` ` `// If size(P) < k, k factors are not possible` ` ` `if` `(P.Count < k)` ` ` `{` ` ` `Console.WriteLine(` `"-1"` `);` ` ` `return` `;` ` ` `}` ` ` `// printing first k-1 factors` ` ` `for` `(` `int` `i = 0; i < k - 1; i++)` ` ` `Console.Write(P[i]+` `", "` `);` ` ` `// calculating and printing product of rest` ` ` `// of numbers` ` ` `int` `product = 1;` ` ` `for` `(` `int` `i = k - 1; i < P.Count; i++)` ` ` `product = product*(` `int` `)P[i];` ` ` `Console.WriteLine(product);` `}` `// Driver code` `static` `void` `Main()` `{` ` ` `int` `n = 54, k = 3;` ` ` `kFactors(n, k);` `}` `}` `// This code is contributed by chandan_jnu` |

## PHP

`<?php` `// PHP program to find if it is possible to` `// write a number n as product of exactly k` `// positive numbers greater than 1.` `// Prints k factors of n if n can be written` `// as multiple of k numbers. Else prints -1.` `function` `kFactors(` `$n` `, ` `$k` `)` `{` ` ` `// A vector to store all prime` ` ` `// factors of n` ` ` `$P` `= ` `array` `();` ` ` `// Insert all 2's in vector` ` ` `while` `(` `$n` `% 2 == 0)` ` ` `{` ` ` `array_push` `(` `$P` `, 2);` ` ` `$n` `= (int)(` `$n` `/ 2);` ` ` `}` ` ` `// n must be odd at this point` ` ` `// So we skip one element (i = i + 2)` ` ` `for` `(` `$i` `= 3; ` `$i` `* ` `$i` `<= ` `$n` `; ` `$i` `= ` `$i` `+ 2)` ` ` `{` ` ` `while` `(` `$n` `% ` `$i` `== 0)` ` ` `{` ` ` `$n` `= (int)(` `$n` `/ ` `$i` `);` ` ` `array_push` `(` `$P` `, ` `$i` `);` ` ` `}` ` ` `}` ` ` `// This is to handle when n > 2 and` ` ` `// n is prime` ` ` `if` `(` `$n` `> 2)` ` ` `array_push` `(` `$P` `, ` `$n` `);` ` ` `// If size(P) < k, k factors are` ` ` `// not possible` ` ` `if` `(` `count` `(` `$P` `) < ` `$k` `)` ` ` `{` ` ` `echo` `"-1\n"` `;` ` ` `return` `;` ` ` `}` ` ` `// printing first k-1 factors` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$k` `- 1; ` `$i` `++)` ` ` `echo` `$P` `[` `$i` `] . ` `", "` `;` ` ` `// calculating and printing product` ` ` `// of rest of numbers` ` ` `$product` `= 1;` ` ` `for` `(` `$i` `= ` `$k` `- 1; ` `$i` `< ` `count` `(` `$P` `); ` `$i` `++)` ` ` `$product` `= ` `$product` `* ` `$P` `[` `$i` `];` ` ` `echo` `$product` `;` `}` `// Driver Code` `$n` `= 54;` `$k` `= 3;` `kFactors(` `$n` `, ` `$k` `);` `// This code is contributed by mits` `?>` |

## Javascript

`<script>` `// javascript program to find if it is possible to` `// write a number n as product of exactly k` `// positive numbers greater than 1.` ` ` `// Prints k factors of n if n can be written` ` ` `// as multiple of k numbers. Else prints -1.` ` ` `function` `kFactors(n , k) {` ` ` `// A vector to store all prime factors of n` ` ` `var` `P = Array();` ` ` `// Insert all 2's in list` ` ` `while` `(n % 2 == 0) {` ` ` `P.push(2);` ` ` `n = parseInt(n/2);` ` ` `}` ` ` `// n must be odd at this point` ` ` `// So we skip one element (i = i + 2)` ` ` `for` `(i = 3; i * i <= n; i = i + 2) {` ` ` `while` `(n % i == 0) {` ` ` `n = parseInt(n/i);` ` ` `P.push(i);` ` ` `}` ` ` `}` ` ` `// This is to handle when n > 2 and` ` ` `// n is prime` ` ` `if` `(n > 2)` ` ` `P.push(n);` ` ` `// If size(P) < k, k factors are` ` ` `// not possible` ` ` `if` `(P.length < k) {` ` ` `document.write(` `"-1"` `);` ` ` `return` `;` ` ` `}` ` ` `// printing first k-1 factors` ` ` `for` `(i = 0; i < k - 1; i++)` ` ` `document.write(P[i] + ` `", "` `);` ` ` `// calculating and printing product` ` ` `// of rest of numbers` ` ` `var` `product = 1;` ` ` `for` `(i = k - 1; i < P.length; i++)` ` ` `product = product * P[i];` ` ` `document.write(product);` ` ` `}` ` ` `// Driver code` ` ` ` ` `var` `n = 54, k = 3;` ` ` `kFactors(n, k);` `// This code is contributed by gauravrajput1` `</script>` |

**Output:**

2, 3, 9

This article is contributed by **Pratik Chhajer**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**