K Factorization

                            Solution in C :

In C  :







#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void calculate ( long target, long *a, long a_len, long *v ) {
  long x,y,rv;
  for (x=0;x<a_len;x++) {
    if (target==a[a_len-1-x]) {
      v[0] = a[a_len-1-x];
      v[1] = 0;
      return;
    } else if ((target%a[a_len-1-x])==0) {
      calculate(target/a[a_len-1-x],a,a_len,v);
      y=0; while(v[y]!=0) { y++; } v[y]=a[a_len-1-x]; v[y+1]=0;
      return;
    }
  }

}

void local_sort ( long *v, long v_len ) {
  long x,y,temp;
    
  for (x=1;x<v_len;x++) {
    y=x-1; while ((y>=0)&&(v[x]<v[y])) { y--; }
    temp = v[x];
    if (v[x]<v[y]) {
      memmove(&(v[y+1]),&(v[y]),(x-y)*sizeof(long));
      v[y] = temp;
    } else if (y<x-1) {
      memmove(&(v[y+2]),&(v[y+1]),(x-y)*sizeof(long));
      v[y+1] = temp;
    }
  }
  return;
}


int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    long V,N,*a,x,ans,pos;
    long *sol;
    
    sol = (long *)malloc(64*sizeof(long));
    memset(sol,0,64*sizeof(long));
    
    scanf("%ld %ld\n",&V,&N);
    a = (long *)malloc(N*sizeof(long));
    pos = 0;
//printf("READ: ");
    for (x=0;x<N;x++) {
      scanf("%ld",&(a[pos]));
//printf("%ld (%ld),",a[pos],V%a[pos]);        
      if ((V%a[pos])==0) {
        pos++;
      }
    }
//printf("\n");
    
//printf("DIVISIBLE: "); for (x=0;x<pos;x++) { printf("%ld ",a[x]); } printf("\n");
    
    local_sort(a,pos);

//printf("SORT: "); for (x=0;x<pos;x++) { printf("%ld ",a[x]); } printf("\n");

    calculate(V,a,pos,sol);
//printf("SOLUTION:\n");
    
    x=0;
    ans = 1;
    while (sol[x]!=0) { ans *= sol[x]; x++; }
    
    if (ans==V) {
      x=0;
      ans = 1;
      printf("%ld ",ans);
      while (sol[x]!=0) {
        ans *= sol[x];
        printf("%ld ",ans); x++;
      }
      printf("\n");
    } else {
      printf("-1\n");
    }
    
    return 0;
}
                        

                        Solution in C++ :

In  C++  :






#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

bool isLess(const vector<uint32_t>& left, const vector<uint32_t>& right){
	if (left.size() != right.size()) return left.size()<right.size(); 
	for(int i=0; i<left.size(); i++){
		if (left[i]!=right[i]) return left[i]<right[i]; 
	}
	return false; 
}

bool eval(const uint32_t N, const vector<uint32_t>& vals, 
	vector<uint32_t>& answer, vector<uint32_t> current){
	if (N==1){
		sort(current.begin(), current.end()); 
		if (answer.empty()) answer = current; 
		else if (isLess(current, answer)) answer.swap(current); 
		return true; 
	}
	if (answer.size()>0 && current.size()>=answer.size()) return false; 
	bool retval = false; 
	for(int i=vals.size()-1; i>=0; i--){
		if (vals[i]<=N && (N%vals[i])==0){
			current.push_back(vals[i]); 
			retval |= eval(N/vals[i], vals, answer, current); 
		}
	}
	return retval; 
}

int main(void){
	uint32_t N; 
	cin >> N; 	// 1 - 1,000,000,000
	int K; 
	cin >> K; // 1 - 20
	vector<uint32_t> vals(K); 
	for(int i=0; i<K; i++) cin >> vals[i]; // each 2 - 20 and distinct
	sort(vals.begin(), vals.end()); 

	vector<uint32_t> answer, temp; 
	if (eval(N, vals, answer, temp)){
		uint32_t v = 1; 
		cout << v << " "; 
		for(int i=0; i<answer.size(); i++){
			v *= answer[i]; 
			cout << v << " "; 
		}
		cout << endl; 
	} else {
		cout << -1 << endl; 
	}
	return 0; 
}
                    

                        Solution in Java :

In  Java :







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int c = s.nextInt();
        
        int[] arr = new int[c];
        for(int i=0; i<c; i++) {
            arr[i] = s.nextInt();
        }
        String out = cal(arr, n, 0, "" + n, new String[1] );
        System.out.println(out == null ? -1 : out);
    }
    
    static String cal(int[] arr, int result, int step, String output, String[] strs) {
        if(strs[0] != null && strs[0].length() < output.length()) {
            return null;
        }
        
        if(result == 1) {
            strs[0] = output;
            return output; 
        } 
        
        String out = null;
        for(int i = 0; i<arr.length; i++) {
            if(result % arr[i] ==0) {
                String temp = cal(arr, result / arr[i], step + 1,result / arr[i] + " " + output, strs);
                if(temp == null) {
                    continue;
                } else if(out == null) {
                    out = temp;
                } else {
                    out = out.length() < temp.length() ? out : temp;
                }
            }
        }
        
        return (out == null) ? null : out;
    }
}
                    

                        Solution in Python : 
                            
In  Python3 :






def getResult(n, a):
    
    if n is 1:
        return []
    
    for x in a:
        if n % x is 0:
            break
    else:
        return False
    
    for x in a:
        if n % x is 0:
            result = getResult(int(n/x), a)
            # print("result is ", result, "for", n/x, "with", a)
            if result is not False:
                result.append(x)
                return result

    return False

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

result = getResult(n, a)
if result is False:
    print(-1)
else:
    current = 1
    print(current, end=' ')
    for x in result:
        current *= x
        print(current, end=' ')