Find if n can be written as product of k numbers

0 0 7 minutes read

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 than 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

Time Complexity: O(?n log n)
Auxiliary Space: O(n)

This article is contributed by Aarti_Rathi and Pratik Chhajer. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek 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.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!