Euler noted the sequence of values of p(n)=n2+n+41 for n=0,...,39 consists entirely of primes. But for n=40 and for n=41, it's trivially divisible by 41.
Is there a (nonconstant) polynomial which gives only prime values?
No. (The proof is apparently due to Goldbach (the same guy with the Conjecture)). Let f(n)∈Z[n] be any polynomial with integer coefficients. Suppose f(n) takes on only prime values (we allow -1,+1 to be considered prime here; it doesn't change anything). Then p=f(1) is prime. Note that for j≥0 and integer k we have that (1+kp)j-1 | p (is divisible by p). This means that f(1+kp)-f(1) | p. Since we assume f(1+kp) prime, we must have f(1+kp)=-p or f(1+kp)=+p. So the polynomial f(n) takes on one of the value +p,-p infinitely many times. But interpolating, we have that f(n) is constant.
In fact, this proof works also for polynomials with more than one variable; no nonconstant polynomial over the integers can take on only prime values.
In the wake of these discoveries in the 18th century, it was surprising when work in mathematical logic (which later led to the amazing final assault of Julia Robinson, Martin Davis, Hilary Putnam and Yuri Matiyasevich to resolve Hilbert's 10th problem) showed an explicit polynomial (in 10 variables) which takes on precisely the set of negative and prime values. That is there is a known polynomial which takes on every prime value, and when it doesn't take on a prime value it takes on a (every) negative value.
See
J.P. Jones, Hideo Wada and Daihachiro Sato and Douglas Wiens, Diophantine representation of the set of prime numbers, Amer. Math. Monthly 83 (1976), 449-464. MR 54:2615
To see this result in its full context, see Matiyasevich's amazing book,
Hilbert's 10th Problem.
The proof has nothing to do with primes; every recursively enumerable set may be expressed in this form!