Concatenating Primes

Question

Challenge:

You are given a string containing only digits. Your task is to output the minimum number of primes which must be concatenated to form the string. If this is impossible, output 0.

Test Cases:

Input -> Output:

252 -> 3
235 -> 2
92 -> 0
31149 -> 2

Answer 1

JavaScript (ES6), 123 121 120 bytes

f=(s,v)=>(p=n=>--n-1?s%n&&p(n):1)(s)||[...s].map((_,i)=>!(n=i&&(a=f(s.slice(0,i)))&&(b=f(s.slice(i)))&&a+b)|n>v?0:v=n)|v

Saved a byte thanks to @Neil!

Explanation

Takes a single string as input. Due to the prime checking method (recursive trial division), the greatest number that can be safely checked is 13840. Some numbers above this will fail due to the maximum call stack size being exceeded. It does, however, finish instantly for every case it can handle.

f=(s,v)=>
  (p=n=>--n-1?s%n&&p(n):1)(s) // if s is prime, return 1
  ||[...s].map((_,i)=>        // else for each index in s, split s into 2
    !(n=i&&                   // v = return value (initialised to undefined)
      (a=f(s.slice(0,i)))&&
      (b=f(s.slice(i)))&&
      a+b
    )|n>v?0:v=n               // if i, a, b and n are all > 0 and !(n > v), v = n
  )|v                         // cast v to an integer and return it

// Test
var testCases = [ "252", "235", "92", "3149", "24747" ];
document.write("<pre>" + testCases.map(c => c + ": " + f(c)).join("\n"));

Answer 2

MATL, 26 24 bytes

0in:"GUtZq@Z^V10ZA=a?x@.

It takes a few seconds for some of the test cases.

Try it online!

Explanation

0       % Push 0
in:     % Take input. Generate array [1,2,...,N] where N is input length
"       % For each. In each iteration the number of used primes is increased
  GU    %   Push input. Convert to number
  tZq   %   Duplicate. Array of primes smaller than the input
  @     %   Push number of primes to bes tested in this iteration
  Z^    %   Cartesian power
  V     %   Convert to 2D array. Each row is a combination of primes
  10ZA  %   Convert each row to base 10, disregarding spaces
  =a    %   Do any of the results equal the input number? 
  ?     %   If so
    x   %     Remove the 0 that's at the bottom of the stack
    .   %     Break for each loop
        %   Implicitly end if
        % Implicitly end for each
        % Implicitly display

Answer 3

Pyth - 19 17 16 bytes

lhf.AmP_sdTa./zY

Test Suite.

Answer 4

Pyth, 16 bytes

lhaf!f!P_sYT./zY

Test suite

Explanation to follow.

Answer 5

Bash + coreutils, 169 158 149 bytes

c()
{
test $1||echo a
for i in `seq ${#1}`
do factor ${1::$i}|grep -q ': \w*$'&&printf b%s\\n `c ${1:$i}`
done
}
c $1|sort|sed '/a/!d;s/..//;q'|wc -c

We count in unary, outputting a line with one b for each prime and a terminating a at the end of line (so that printf has a token to work with).

The primality test is factor $n | grep -q ': \w*$', which determines whether the number has exactly one prime factor.

We recursively partition the input; if the left half is prime, we filter the results of the right half by adding one to each value. Returning a for a zero-length input terminates the recursion.

Finally, we take all the results and sort to find the shortest (ignoring any that don't have the a to indicate success); we must delete two (for the inserted a and for the newline), then count characters to give the result.

Tests

$ for i in 252 235 92 31149 111; do echo "$i:"$'\t'"$(./77623.sh $i)"; done
252:    3
235:    2
92:     0
31149:  2
111:    0

I added 111 to the tests to show that 1 is correctly considered non-prime.

Answer 6

Mathematica, 142 135 bytes

Min[Length/@Select[Join@@@Permutations/@IntegerPartitions@Length[a=#],And@@PrimeQ@*FromDigits/@a~Internal`PartitionRagged~#&]]/.∞->0&

As you can see, Mathematica was not built for this task. Takes a list of digits.