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
Where is this question ? What are constraints ?
String length : 10^7
Question is from my campus interview
Reading string of that length will give TLE in most cases 
That is what the interviewer told me , you can assume it to not give TLE and proceed with the approach.
Even if it is brute force , we would have to generate all possible subsequences ? I am not able to come up with a good solution .
Brute force is the way to go, to check if the number is prime or not, that can be done in O(1),
though I think there might exist a solution which uses digit DP but seems unlikely. Will think.
Yeah because i guess we would have to find all possible combinations from the numbers at hand , and at worst case there could be more than n! combinations
His question is practically wrong and has no solution,
you said string can be of the length 10000000.
Means the prime number can have 10^7 digits as well.
To check if such a big number which has 10^7 or more digits…is prime or not…is out of the scope of computer science.
Kudos to the interviewer!
lol ok ,
But theoretically speaking, please still let me know what could bet the best possible solution.
Thanks!
If the string length is more than 15-16, there exists no solution …as you can never know that a number as great as 10^16 is prime or not without the compiler going mad.
The obvious solution is simple brute-force + sieve 
for string-length< 15
There are methods to check huge numbers are prime or not.
Your reply Should be “it’s impossible”
Theoretically or practically 
10^7 digits will have 2^(10^7) numbers.
And how will you iterate 2^(10^7) values ?
I think you interviewer was kidding with you and wanted to check if you know big O notation and capacity of any normal Computer.
Say, I have to check numbers with 10^6 digits…if they are prime or not, can you check such 10 numbers in under 0.5 second? Good
I wish I was as high as the interviewer
Let me know that too
Say, the question is find all the different prime numbers from the string by taking the subsets…
But prime number should always be less than 10.
Solution:-Just count the occurrence of 2,3,5,7 and that is your answer.
For prime<100, its easy to calculate it, @l_returns God will tell you for sure
Prime number - Wikipedia
Check primality tests.
And I never said it’s possible with 10^6 digits.
You said it’s not possible for values are greater than 10^15 or 10^16 
What I am saying is it’s not correct.
Nope we won’t
Find it on your own
Since you don’t have any proof of source 