# Concatenating Primes

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

• Related Apr 12, 2016 at 2:04
• Can there be leading zeroes? Apr 12, 2016 at 3:04
• Yes, there can be leading zeroes. Apr 12, 2016 at 3:05
• Can we take a list of digits? Apr 12, 2016 at 11:53
• What happens if there are leading zeroes? Apr 12, 2016 at 18:38

# JavaScript (ES6), 123121 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"));

• Is it me or can you change i?(a=...)&&(b=...)&&a+b:0 to i&&(a=...)&&(b=...)&&a+b?
– Neil
Apr 12, 2016 at 7:43

# 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


# Pyth, 16 bytes

lhaf!f!P_sYT./zY


Test suite

Explanation to follow.

# Pyth - 1917 16 bytes

lhf.AmP_sdTa./zY

• In its newer form, this one counts 0 and 1 as primes. However, before the edit, it did not. Apr 12, 2016 at 0:30
• @poi830 fixed it. Apr 12, 2016 at 0:31

# Bash + coreutils, 169158 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.

• I was going to suggest this. Most of my modifications are probably obsolete now, but others should still work. Apr 12, 2016 at 17:29
• @Dennis - I like the c to generate the final 0. Not so keen on the copious stderr, though. You're welcome to use (versions of) my answer as a basis for your own if you like. Apr 12, 2016 at 17:38

# Mathematica, 142 135 bytes

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


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

• Can you use And@@ instead of AllTrue? Should save 4-5 bytes. Apr 12, 2016 at 20:39
• Flatten[#,1]=Join@@@# Apr 12, 2016 at 20:41
• Um...gives error and wrong answer on 133...you did use all test cases, right? Apr 12, 2016 at 20:43
• @CatsAreFluffy Golfed and clarified. Apr 12, 2016 at 21:00

# Stax, 18 bytes

¬∞ÿ╔>÷▀↓☼~î☼ó♀RàEx
`

Run and debug it