Decomposing into primes 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 -&gt; 1
55 -&gt; 1 
3593 -&gt; 4 (359 and 3, or 3 and 593, or 3 and 59 and 3, or 3593)
3079 -&gt; 2 (3 and 079, or 3079)
119 -&gt; 0 
5730000037 -&gt; 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-&gt; 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
Haskell, 96 89 bytes

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



p x=[1|0&lt;-mod x&lt;$&gt;[2..x]]==[1]
f[]=1
f b=sum[f$drop i b|i&lt;-[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&lt;-mod x&lt;$&gt;[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 Li represents the last i digits of our input (lets call it n).

We define L0 to have a value of 1 and each other value in L to have the sum of each Lj such that j &lt; 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. (Lk where k is the number of digits of n)