Husk, 6 bytes

→fṗmrQ

Try it online!

Japt -h, 6 bytes

ã f_°j

Try it

Jelly, 6 bytes

DẆḌẒƇṀ

Try it online!

Takes input as an integer. If input must be a string, then 7 bytes. Returns 0 for numbers with no primes in them.

How it works

DẆḌẒƇṀ - Main link. Takes n on the left
    Ƈ  - Find...
     Ṁ - ...the largest...
 Ẇ     - ...contiguous...
  ḌẒ   - ...prime...
D      - ...in a string

or, alternatively,

DẆḌẒƇṀ - Main link. Takes n on the left
D      - Convert n to digits
 Ẇ     - Get all contiguous sublists
  Ḍ    - Convert each back from digits
    Ƈ  - Filter keep:
   Ẓ   -   Primes
     Ṁ - Yield the maximum

Perl 6 (40 characters, 41 bytes)

$_=get;say max grep &is-prime,+«m:ex/.+/

First get input into $_, this makes the regex match call shorter. :ex gives exhaustive matching for regex, it will give all possibilities. The hyper op +« (or +<< works too) will make numbers out of the Match objects, those are passed to grep with &is-prime sub as selector. Finally take the maximum of the remaining list and output it.

Perl 6 (50 characters, 51 bytes)

say max +«get.match(/(.+)<?{(+$0).is-prime}>/,:ex)

+« maps strings to numbers, max gets the biggest number, get receives a line. /(.+)<?{(+$0).is-prime}>/ is a regular expression that gets all primes <?{}> is a code assertion. is-prime is Int class method which checks if number is a prime. I need to cast value to number by using +, because it's Str by default. :ex means that it tries to find ALL matches (including those where overlap others). Because of Rakudo Perl bug, it's currently impossible to use m// here.

This works for any number, and if you remove max (or replace it with sort) you will get list of all primes in the number, for extra bonus (not that this gives points, or anything). For example (with sort in this case):

1234567890
2 3 5 7 23 67 89 4567 23456789

J (24 22)

Reading from the keyboard is actually shorter than defining a function.

>./(*1&p:);"..1!:1[1

Test:

   >./(*1&p:);"..1!:1[1
3571
3571
   >./(*1&p:);"..1!:1[1
46462
2
   >./(*1&p:);"..1!:1[1
1236503
236503
   >./(*1&p:);"..1!:1[1
4684
0
   >./(*1&p:);"..1!:1[1
4680
0
   >./(*1&p:);"..1!:1[1
twelve monkeys is a pretty good movie
__

Explanation:

• 1!:1[1: read a line of text from the keyboard
• "..: the evaluation (".) of each suffix (.) of each prefix () of the string.
• ;: flatten the matrix
• *1&p:: multiply each value by whether it is a prime or not (so all nonprimes will be zero)
• >./: get the largest value in the list

Scala (83 chars)

I wasn't sure how to provide inputs to the program so I considered n is the input. Here's the actual solution (based on which the solution length is evaluated). Below that is an executable form of the solution (which isn't golfed yet) for execution along with the output (for the samples give OP has).

Solution:

n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max

Executable solution:

object A {
  def main(x:Array[String])=List("3571","123","23","1236503","46462","4684","460","4601","12 monkeys..").foreach(e=>println(e+" => "+q(e)))

  private def p(n: String)=n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max
  private def q(n: String)=try p(n)catch{case e=>e.toString}
}

Sample output:

3571 => 3571
123 => 23
23 => 23
1236503 => 236503
46462 => 2
4684 => java.lang.UnsupportedOperationException: empty.max
460 => java.lang.UnsupportedOperationException: empty.max
4601 => 601
12 monkeys.. => java.lang.NumberFormatException: For input string: "12 "

Explanation:

Steps are pretty straight forward.

input -> Find all substrings -> filter non primes -> find longest value

• main(Array[String]): Method provides sample input and executes method q(String) for each input
• q(String): Wraps actual program logic from p(String) so any exceptions are appropriately reported. Helps in formatting the output better because invalid inputs are going to get NumberFormatExceptions where as the lack of a prime will throw an UnsupportedOperationException
• p(String): Actual logic of the program. Let's split the explanation for this into parts
  • n.inits: Creates an Iterator to iterate over the String input (n)
  • flatMap(f): Applies an operation on the Iterator and pushes the result into a List
    • _.tails.toList.init.map(BigInt(_)): Splits the String and removes empty Strings from the resultant List. Finally converts the String to a BigInt which is an equivalent of java.math.BigInteger. For golfing reasons, BigInt is selected (shorter name).
  • filter(f): if f returns false, the value is removed from the resultant List
    • _ isProbablePrime 1: This line could have been written as _.isProbablePrime(1) but the representation used saves 1 byte. This line actually checks if the value is a prime (probabilistically; since certainty is set to 1, execution time goes up but the system makes certain (more or less) that the number is a prime.
  • max: Finds the maximum value (not String based length. Actual max value)

Haskell, 94

main=getLine>>=print.maximum.filter(x->and$map((0/=).mod x)[2..x-1]).map read.init.scanr(:)[]

Ruby 61

Take all primes up to N and see if they are in the string

require'prime'
p Prime.each(gets.to_i).select{|i|~/#{i}/}.max

^{I think this only works on Ruby 1.9 and newer, but I'm not sure.}

Mathematica 67 47

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&

Explanation

The code is a pure function. It has no name. In it, # represents the full input string.

StringCases takes the input, #, and checks for substrings, a, of one character or more (that's why __ was used instead of _) that are primes; PrimeQ must return True for the substring.

All the favorable cases, i.e. the substrings that are primes, are by default returned in a list. 〚1〛, or [[1]] takes the first part, that is, the first element of that list of primes. element[[1]] is shorthand for Part[element, 1]. If there is more than one prime, the first one will be the longest prime (StringCases checks the longest substrings first).

Examples

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&["1236503"]

"236503"

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&/@ 
{"1236503", "123", "46462", "4684", "460", "4601", 
"12 monkeys is a pretty good movie, but not as good as se7en"}

{"236503", "23", "2", {}[[1]], {}[[1]], "601", "2"}

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).

Python 2.7 - 84

Here is a reference implementation to beat, I used it for the example output in the question, so its gauranteed to work ^{* Not an actual guarantee}

Shameless improvement based on Ben Reich's much better solution than my original one. With major assistance from Volatility

N=input()
print max(x for x in range(N+1)if(`x`in`N`)&all(x%i for i in range(2,x)))

Prior incantations of the second line include:

print max(x for x in range(N+1)if`x`in`N`and 0 not in(x%i for i in range(2,x)))
print max(x for x in range(N+1)if`x`in`N`and sum(x%i<1 for i in range(2,x))<1)

---

The original version - 143

N=`input()`
p=lambda n:[n%i for i in range(2,n)if n%i==0]
print max(int(N[j:i])for i in range(len(N)+1)for j in range(i)if not p(int(N[j:i])))