What about Goldbach conjecure asking if every even natural number is the sum of two primes?
Another quite famous problem is Collatz' conjecture (also known as $3n+1$ problem), see http://en.wikipedia.org/wiki/Collatz_conjecture: consider the algorithm taking $n\in\mathbb{N}$ and sending it to $n/2$ if $n$ is even, and to $3n+1$ if $n$ is odd, iteratively. The question is whether the algorithm always ends up producing the loop $1\mapsto 3\cdot 1+1=4\mapsto 2\mapsto 1\mapsto 4\dots$ regardless of the initial input $n$.
