Decomposing into primes

Question

Given an integer n, return the number of ways that n can be written as a list of prime numbers. For example, 2323 can be written as (2,3,23), (23,23) or (2,3,2,3) or (23,2,3), so you would output 4. If it can not be written in this way, you should output 0.

A prime number such as 019 or 00000037 is a valid prime for this problem.

Test cases:

5 -> 1
55 -> 1 
3593 -> 4 (359 and 3, or 3 and 593, or 3 and 59 and 3, or 3593)
3079 -> 2 (3 and 079, or 3079)
119 -> 0 
5730000037 -> 7 (5,7,3,000003,7, 5,7,3,0000037, 5,73,000003,7, 5,73,0000037, 5,73000003,7, 5,7,30000037, 5730000037)
0-> undefined (you do not have to handle this case)

This is code-golf, so the shortest answer in bytes in each language wins!

Edit: now I know why I should use the sandbox next time

Answer 1

Haskell, 96 89 bytes

5 bytes saved thanks to H.PWiz's primality test

p x=[1|0<-mod x<$>[2..x]]==[1]
f[]=1
f b=sum[f$drop i b|i<-[1..length b],p$read$take i b]

Try it online!

Explanation

The first thing that's done is creating a prime test function using Wilson's theorem using the definition of prime.

p x=[1|0<-mod x<$>[2..x]]==[1]

Then begin defining f. The first thing I thought when I saw this problem was to use dynamic programming. However dynamic programming costs bytes so this uses a "psuedo-dynamic programming" algorithm. Whereas in dynamic programming you would store a Directed Acyclic graph in memory here we just use recursion and recalculate each node every time we need it. It loses all of the time benefits of dynamic programming, but this is code-golf so who cares. (still better than brute force search though)

The algorithm is as follows, we construct a Directed Acyclic Graph, L, where each node represents a substring of the number. In particular L_i represents the last i digits of our input (lets call it n).

We define L₀ to have a value of 1 and each other value in L to have the sum of each L_j such that j < i and the substring of n from i to j is prime.

Or in a formula:

We then return the value at the largest largest index of L. (L_k where k is the number of digits of n)

Answer 2

Jelly, 8 bytes

ŒṖḌÆPẠ€S

Try it online!

-1 byte thanks to Leaky Nun
-1 byte thanks to Dennis

Explanation

ŒṖḌÆPẠ€S  Main Link
ŒṖ        List Partitions (automatically converts number to decimal digits)
  Ḍ       Convert back to integers (auto-vectorization)
   ÆP     Are they primes? (auto-vectorization)
     Ạ€   For each, are they all truthy (were the numbers all primes?); 1/0 for truthy/falsy
       S  Sum; gets number of truthy elements

Answer 3

Brachylog, 10 bytes

ṫ{~cịᵐṗᵐ}ᶜ

Try it online!

First ṫ converts the input into a string. {…}ᶜ Counts the number of possible outputs for ….

Inside {…} the output of ṫ is fed to ~c. The output of this predicate satisfies that, when concatenated, it is equal to the input. This is fed into ịᵐ, which specifies that its output is it's input with each string converted into an integer. ṗᵐ specifies that its input consists of primes

Answer 4

Pyth, 13 bytes

lf.AmP_sdT./`

Test suite.

Answer 5

Python 2, 105 95 91 bytes

f=lambda n:sum(0**k|f(n%10**k)for k in range(n)if sum(n/10**k%j<1for j in range(1,n+2))==2)

This is very slow.

Try it online!

Answer 6

Python 2, 161 bytes

lambda n:sum(all(d>1and all(d%i>0for i in range(2,d))for d in v)for v in g(`n`))
g=lambda s:[[int(s[:i])]+t for i in range(1,len(s))for t in g(s[i:])]+[[int(s)]]

Try it online!

The function g creates the partitions recursively (it takes a string as input but outputs a list of lists of ints). Most of the remaining code is just to implement 'is d a prime?'.

Answer 7

Gaia, 12 bytes

₸B¦ṗ¦Π
$ḍ↑¦Σ

Try it online!

Answer 8

Clean, 199 141 131 bytes

import StdEnv
?n|n<2=0|and[gcd n i<2\\i<-[2..n-1]]=1=0
@n#s=toString n
#f=toInt o(%)s
= ?n+sum[@(f(0,i))\\i<-[0..n]| ?(f(i+1,n))>0]

Try it online!

Answer 9

J, 65 64 bytes

(1#.[:*/"1*/@>)@(#`(1,.[:#:[:i.2^#-1:)@.(1<#)(1:p:&.>".);.1])@":

Try it online!

Answer 10

Pyth, 12 bytes

lf*FmP_sdT./    

Takes input as an integer, outputs True or False

Try it online!