25
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – Alex A. Apr 12 '16 at 2:04
  • \$\begingroup\$ Can there be leading zeroes? \$\endgroup\$ – Zgarb Apr 12 '16 at 3:04
  • \$\begingroup\$ Yes, there can be leading zeroes. \$\endgroup\$ – poi830 Apr 12 '16 at 3:05
  • \$\begingroup\$ Can we take a list of digits? \$\endgroup\$ – LegionMammal978 Apr 12 '16 at 11:53
  • 1
    \$\begingroup\$ What happens if there are leading zeroes? \$\endgroup\$ – Dennis Apr 12 '16 at 18:38
6
\$\begingroup\$

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"));

\$\endgroup\$
  • \$\begingroup\$ Is it me or can you change i?(a=...)&&(b=...)&&a+b:0 to i&&(a=...)&&(b=...)&&a+b? \$\endgroup\$ – Neil Apr 12 '16 at 7:43
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Pyth, 16 bytes

lhaf!f!P_sYT./zY

Test suite

Explanation to follow.

\$\endgroup\$
4
\$\begingroup\$

Pyth - 19 17 16 bytes

lhf.AmP_sdTa./zY

Test Suite.

\$\endgroup\$
  • \$\begingroup\$ In its newer form, this one counts 0 and 1 as primes. However, before the edit, it did not. \$\endgroup\$ – poi830 Apr 12 '16 at 0:30
  • 1
    \$\begingroup\$ @poi830 fixed it. \$\endgroup\$ – Maltysen Apr 12 '16 at 0:31
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I was going to suggest this. Most of my modifications are probably obsolete now, but others should still work. \$\endgroup\$ – Dennis Apr 12 '16 at 17:29
  • \$\begingroup\$ @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. \$\endgroup\$ – Toby Speight Apr 12 '16 at 17:38
2
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.