There are two
equations which are an
algebraic expression of this
sieve:
k+1 is prime iff for all natural numbers u,v:
(1)k <> u*v + u + v
Equation (1) is read "k does not equal u times v plus u plus v". The second equation yields only the odd primes:
2*k+1 is prime iff for all natural numbers u,v:
(2)k <> 2*u*v + u + v
One thing to notice. k=2*n satisfies equation (1) for some n iff k=n satisfies equation (2).
There are similar equations describing primes in terms of b*k+/-c ("+/-" is to be read "plus or minus") for all naturals b, and each one has an accompanying equation 2*b*k+/-c which describes the primes in the same manner. As b increases, however, more and more work must be done with
modulo operations to ensure that the
numbers are indeed prime, and that all primes are covered.
The
mathematics for the above
equations are as follows:
A number n+1 is composite for n in the natural numbers iff there exists a k>1 in the natural numbers such that k divides n and k<n.
A number k divides a number n iff there exists an x in the integers such that k*x = n.
So test n with k which are greater than one. If k is in the set of naturals, then use k+1 for tests. Similarly, use x+1 for x in the naturals.
Thus, a number n+1 is composite iff there exist an x and a k in the naturals such that n+1 = (k+1)*(x+1).
The negation of the above is to say that a number n+1 is prime iff for all x and k in the naturals, n+1 != (k+1)*(x+1), which is the same as saying n+1 != k*x+k+x+1, which is the same as n != k*x+k+x.
Similar logic applies for 2*n+1.