Turing Machine to return all prime numbers
Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient.

The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow:


Start with $n=2$ - this is prime.
Set $j$ equal to $n$.
Add $1$ to $n$
Set $k$ equal to $n$.
Subtract $j$ from $k$.
If $k$ is greater than $0$ go to step $5$.
If $k$ equals $0$ then $n$ is not prime; go to step $2$.
Subtract $1$ from $j$.
If $j$ equals $1$ then $n$ is prime; go to step $2$.
Go to step $4$.