By definition, how is a prime number represented? Even numbers can be easily represented as $2n$. Odd numbers as $2n+1$. An exactly divisible operation can be defined as $n = dq$.  
But, is there an specific way of representing a prime number, obtained by a proof of some sort? 
 A: From Jones, J., Sato, D., Wada, H. and Wiens, D. (1976). Diophantine representation of the set of prime numbers. American Mathematical Monthly, 83, 449-464.
The set of prime numbers is identical with the set of positive values taken on by the polynomial
$(k+2)(1-(wz+h+j-q)^2-((gk+2g+k+1)\cdot(h+j)+h-z)^2-(2n+p+q+z-e)^2-(16(k+1)^3\cdot(k+2)\cdot(n+1)^2+1-f^2)^2-(e^3\cdot(e+2)(a+1)^2+1-o^2)^2-((a^2-1)y^2+1-x^2)^2-(16r^2y^4(a^2-1)+1-u^2)^2-(((a+u^2(u^2-a))^2-1)\cdot(n+4dy)^2+1-(x+cu)^2)^2-(n+l+v-y)^2-((a^2-1)l^2+1-m^2)^2-(ai+k+1-l-i)^2-(p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m)^2-(q+y(a-p-1)+s(2ap+2a-p^2-2p-2)-x)^2-(z+pl(a-p)+t(2ap-p^2-1)-pm)^2)$
as the variables range over the nonnegative integers.
A: $$P:= \{p \in \mathbb{N}: \forall c \in \mathbb{N}, (c|p \Rightarrow (c = p \lor c = 1)) \}$$
Is that what you're looking for? Or maybe you were thinking of something along the line of Euclid's Lemma...?
$$P = \{ p \in \mathbb{N} : \forall a,b \in \mathbb{N}, p|ab \Rightarrow (p|a \lor p|b) \}$$
A: Rowland's formula for the primes generates only 1's and primes.  (See this blog post for a discussion.  The paper can be found here.)
Let $a(1)=7$ and $a(n)=a(n-1)+\gcd(n,a(n-1))$ for $n\ge 2,n\in\mathbb{N}$.  Then $a(n)-a(n-1)$ is either 1 or prime.
Another formula, due to Benoit Cloitre (see this blog post), also gives only 1's and primes.
Let $b(1)=1$ and $b(n)=b(n-1)+\mathrm{lcm}(n,b(n-1))$ for $n\ge 2,n\in\mathbb{N}$.  Then $b(n)/b(n-1)-1$ is either 1 or prime.
A: Try an adder process based on 30n
30n+/-1 30n+/-7 30n+/-11 30n+/-13
This eliminates a large number of composites and leaves 8 columns of primes.
A little work and a lot of replication knocks the list down even more.
7*11 7*41 7*71 7*101
Etc eliminates a string of composites in the 30n-13 column again intensive but does eliminate all the composites from the list leaving only the primes.
Same with
17*23 17*53 17*83 17*113 Etc....
eliminates a string of composites in the 30n+7 column
An extensive list of all primes is need to prove a large mersennes value.
Quite a gem for smaller values if you need to determine a larger value finding which 30n column the number belongs in first simplifies the proocess significantly
