Find the largest contiguous prime in a string In fairness, this is based on a StackExchange question - but its a good question.

The challenge is fairly simple:


Take a string of numerals
Find and print the largest contiguous prime number in the string


Scoring:


Lowest number of characters wins.
Victor will likely be a golfscript entry but we won't hold that against them, cause we all have fun and learn things, right.
Winner we be awarded when I notice that I haven't actually ticked the green button.


Assumptions:


The string is only numbers


If the string contains letters, you may have undefined behaviour

The string contains at least 1 prime


If the string does not contains 1 valid prime number, you may have undefined behaviour

Speed is not a constraint


Use a shorter prime algorithm over a faster one.
If your entry eventually finishes, thats ok, just make sure it will provable happen before the heat death of the universe.

The length of the string can be assumed less than 15 characters long


For example:

&gt;&gt; Input:  3571
&lt;&lt; Output: 3571

&gt;&gt; Input:  123
&lt;&lt; Output: 23

&gt;&gt; Input:  1236503
&lt;&lt; Output: 236503

&gt;&gt; Input:  46462
&lt;&lt; Output:  2

&gt;&gt; Input:  4684
&lt;&lt; Output: ValueError: max() arg is an empty sequence

&gt;&gt; Input:  460
&lt;&lt; Output: 0   # Note, zero is not a prime, but the above string has no valid prime

&gt;&gt; Input:  4601
&lt;&lt; Output: 601

&gt;&gt; Input:  "12 monkeys is a pretty good movie, but not as good as se7en"
&lt;&lt; Output: ValueError: Fight Club was also good, I find Brad Pitt to be a consistantly good actor.


Possible implementations:


Find all substrings of the input, check if they are prime. - Legostormtroopr (original)
Find all integers less than input, check if they are in the input then check if it is prime - Ben Reich
Take a list of all primes less than the input, check if it is in the input - daniero
GolfScript 40 37

.{`\`?)}+\~),\,{.,(;\{\%!}+,,1=},)\;


This looks at all numbers less than or equal to the the input, filters down to the ones that are substrings of the input, and then filters further down to the primes.  Then, it takes the largest such element (which is obviously guaranteed to have the most digits). 

Let's break it down into two main sections:

.{`\`?)}+\~,\,


This part of the code filters down to all integers string contained in the input.  It uses grave accent to turn numbers into strings, and then ? to determine the index of the substring.  Since ? returns -1 in the case of no containment, increment using ) so that the output is 0 for non-substrings, which will behave nicely with the , filtering. 

{.,(;\{\%!}+,,1=},


This part of the code filters down to the primes by counting the number of factors less than the given number (an integer is a factor only if number factor %! is 1.  A prime number will have exactly 1 factor strictly less than itself, so do 1=. 

Since the numbers are in order, take the last one and clear the stack using )\;

This obviously isn't as efficient as possible (since it somewhat unnecessarily iterates over all integers less than the input), but it still terminates with big input like 1236503 relatively quickly on my computer (1 minute).