12
1
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 < 231
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.
What do you mean by partitioning ? – Optimizer – 2015-01-26T17:41:02.847
@Optimizer Grouping a list into nonoverlapping sublists. Some languages have this built in, such as Mathematica.
– Geobits – 2015-01-26T17:43:17.403Is there a time limit? A particularly naive algorithm could take centuries for a large value of M. Simple things like noting there can only be one factor larger than sqrt(N) obviously help a lot. – Level River St – 2015-01-26T17:51:33.413
1@steveverrill Given the upper limit on N, there should only be 30 (prime) factors max, which speeds things up quite a bit. However, feel free to be naive. If your algorithm is not likely to provide an answer within a few hours, a well-explained proof of concept could help voters decide. – Geobits – 2015-01-26T17:54:39.640
a built in which allows you to do cartesian product of two list is allowed ? – Optimizer – 2015-01-26T18:21:36.863
@Optimizer Yes. – Geobits – 2015-01-26T18:24:32.980
I assume that 1 is not a valid factor? – FUZxxl – 2015-01-27T21:18:48.177
@FUZxxl Correct, see the examples and the opening sentence. – Geobits – 2015-01-27T21:20:34.510