How many ways to write N as a product of M integers?

Question

Given an integer N, count how many ways it can be expressed as a product of M integers > 1.

Input is simply N and M, and output is the total count of distinct integer groups. Meaning you can use an integer more than once, but each group must be distinct (3 x 2 x 2 would not count if 2 x 2 x 3 is present).

Constraints

1 < N < 2³¹
1 < M < 30

Examples

Input 30 2 gives output 3, since it can be expressed 3 ways:

2 x 15
3 x 10
5 x 6

Input 16 3 gives output 1, since there's only one distinct group:

2 x 2 x 4

Input 2310 4 gives output 10:

5 x 6 x 7 x 11
3 x 7 x 10 x 11
3 x 5 x 11 x 14
3 x 5 x 7 x 22
2 x 7 x 11 x 15
2 x 5 x 11 x 21
2 x 5 x 7 x 33
2 x 3 x 11 x 35
2 x 3 x 7 x 55
2 x 3 x 5 x 77

Input 15 4 gives output 0, since it cannot be done.

Rules

Standard code golf loopholes apply, along with standard definitions for input/output. Answers may be a function or full program. Built-in functions for factorization and/or partitioning are not allowed, but others are fine. Code is counted in bytes.

Answer 1

Python 3, 59

f=lambda N,M,i=2:i<=N and f(N/i,M-1,i)+f(N,M,i+1)or-~M==N<2

We count up potential divisors i. With the additional argument i as the lowest allowed divisor, the core recursive relation is

f(N,M,i)=f(N/i,M-1,i)+f(N,M,i+1)

For each i, we either choose to include it (possible as a repeat), in which case we divide the required product N by i and decrement M. If we don't, we increase i by 1, but only if i<N, since there's no use checking divisors greater than N.

When the minimum divisor i exceeds N, there's no more potential divisors. So, we check if we've succeeded by seeing if M==0 and N==1, or, equivalently, M+1==N==1 or M+1==N<2, since when M+1==N, the mutual value is guaranteed to be a positive integer (thanks to FryAmTheEggman for this optimization).

This code will cause a stack overflow for N about 1000 on most systems, but you can run it in Stackless Python to avoid this. Moreover, it is extremely slow because of its exponential recursive branching.

Answer 2

Pyth - 24 23 22 21 bytes

Not a complicated solution. Will be golfing more. Just takes cartesian product of lists and filters. Same strategy as @optimizer (I'm guessing because of his comment, didn't actually decipher that CJam) Thanks to @FryAmTheEggman for 2 bytes and trick with M.

Ml{m`Sdfqu*GHT1G^r2GH

Defines a function g with args G and H

M                    function definition of g with args G and H
 l                   length of
  {                  set (eliminates duplicates)
   m                 map
    `Sd              repr of sorted factors so can run set (on bash escape ` as \`)
    f                filter
     q      G        equals first arg
      u*GHT1         reduce by multiplication
     ^     H         cartesian product by repeat second arg
       r2G           range 2 to first arg

Worked on all test args except last, was too slow on that one but there is no time limit given.

Answer 3

Ruby, 67

f=->n,m,s=2,r=0{m<2?1:s.upto(n**0.5){|d|n%d<1&&r+=f[n/d,m-1,d]}&&r}

Actually reasonably efficient for a recursive definition. For each divisor pair [d,q] of n, with d being the smaller one, we sum the result of f[q,m-1]. The tricky part is that in the inner calls, we limit factors to ones greater than or equal to d so that we don't end up double-counting.

1.9.3-p327 :002 > f[30,2]
 => 3 
1.9.3-p327 :003 > f[2310,4]
 => 10 
1.9.3-p327 :004 > f[15,4]
 => 0 
1.9.3-p327 :005 > f[9,2]
 => 1 

Answer 4

CJam, 48 bytes

This can be a lot shorter but I have added certain checks to make it work for decent number of M on the online compiler.

q~\:N),2>{N\%!},a*{_,2/)<m*{(+$}%}*{1a+:*N=},_&,

Try it online here

Answer 5

T-SQL 456 373

I'm sure this'll break when the inputs are even close to being large.

Thanks to @MickyT for helping to save a lot of characters with CONCAT and SELECTing instead of multiple SETs.

CREATE PROC Q(@N INT,@M INT)AS
DECLARE @ INT=2,@C VARCHAR(MAX)='SELECT COUNT(*)FROM # A1',@D VARCHAR(MAX)=' WHERE A1.A',@E VARCHAR(MAX)=''CREATE TABLE #(A INT)WHILE @<@N
BEGIN
INSERT INTO # VALUES(@)SET @+=1
END
SET @=1
WHILE @<@M
BEGIN
SELECT @+=1,@C+=CONCAT(',# A',@),@D+=CONCAT('*A',@,'.A'),@E+=CONCAT(' AND A',@-1,'.A<=A',@,'.A')END
SET @C+=CONCAT(@D,'=',@N,@E)EXEC(@C)

Answer 6

Jelly, 10 bytes

ḍƇ`ḊœċP€ċ⁸

Try it online!

Assumes that "Built-in functions for factorization and/or partitioning are not allowed" doesn't prohibit the œċ builtin, which is combinations with replacements. If this isn't allowed, we can use a Cartesian product builtin, which is allowed, for 12 bytes: ḍƇ`ḊṗṢ€QP€ċ⁸

How it works

ḍƇ`ḊœċP€ċ⁸ - Main link. Takes n on the left and m on the right
 Ƈ         - Filter the integers, k, between 1 and n where the following is true:
ḍ          -   Does k divide...
  `        -   ...n?
           - This gives a list of divisors
   Ḋ       - Remove the first value, 1
    œċ     - Take all combinations of length m, with replacement
      P€   - Take the product of each
        ċ⁸ - Count occurrences of n