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.
1Related – Alex A. – 2016-04-12T02:04:57.847
Can there be leading zeroes? – Zgarb – 2016-04-12T03:04:55.833
Yes, there can be leading zeroes. – poi830 – 2016-04-12T03:05:40.107
Can we take a list of digits? – LegionMammal978 – 2016-04-12T11:53:20.333
1What happens if there are leading zeroes? – Dennis – 2016-04-12T18:38:15.917
Format of input/output? – Leaky Nun – 2016-04-16T12:11:17.757