**We have been given a string of numbers**

**We have to generate all possible prime from the string of numbers**

Example : “34791”

Some of the possible primes: 3,7,37,41,31,71 etc.

What would be the optimal solution for this ?

Udpate : How would we do this if this was a substring problem ? I am not able to come up with a DP solution.

In that case , all the primes would be 3 7 79 and 91