# 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 -> 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 , so the shortest answer in bytes in each language wins!

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

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 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 < 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) # 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  • I've noticed that 05AB1E can't do this easily. Partitions seems like a great command. – Magic Octopus Urn Dec 19 '17 at 21:40 # 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 • You don't need to convert to string and back, those 7 bytes are enough: {~cṗᵐ}ᶜ. This is really slow because ~c on integers works with constraint arithmetic, but in theory it works. – Fatalize Dec 20 '17 at 12:36 • @Fatalize I think that fails to account for leading zeros – H.PWiz Dec 20 '17 at 12:40 # Pyth, 13 bytes lf.AmP_sdT./  Test suite. • I don't know Pyth that well but instead of filtering and then taking the length, could you do for_each instead of filter and then sum? – HyperNeutrino Dec 19 '17 at 0:34 • @HyperNeutrino does that make any difference? – Leaky Nun Dec 19 '17 at 0:35 • I'm not sure, I haven't tested. It does for Jelly (probably because of the two-byte filter quick) but I'm not sure. – HyperNeutrino Dec 19 '17 at 0:36 • @HyperNeutrino filter is one byte here... – Leaky Nun Dec 19 '17 at 0:37 # Python 2, 10595 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! # 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?'. # Gaia, 12 bytes ₸B¦ṗ¦Π$ḍ↑¦Σ


Try it online!

# Clean, 199141 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!

# J, 65 64 bytes

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


Try it online!

# Pyth, 12 bytes

lf*FmP_sdT./


Takes input as an integer, outputs True or False

Try it online!