Some ways to get a set of primes What would be some easy way to get a set of primes?
I do not want a way to get a complete set of primes; rather, I just want to see a way of getting some subset of primes - which cardinality would still be infinite.
 A: Consider the sequence
$$a_n=a_{n-1}+\gcd(n,a_{n-1}),\ \ a_1=7$$
Then $a_n-a_{n-1}$ is always either a prime or 1. 
The introduction of Eric Rowland's paper on this sequence discusses several other prime generating functions which might be worth looking at.
A: There is no known formula which 


*

*produces infinitely many primes, and 

*produces only primes, and 

*is practical. 
A: How about using Mills' constant?
$\lfloor A^{3^n}\rfloor$ is prime for all positive integers $n$.
While "easy", it does not translate into any practical method.
A: There was an (I think) interesting article in AMM a while back which noted that if you take a product of consecutive primes $\pi_{n=1}^k p_n$ and divide it into two smaller products $\pi_1=\pi_{n=1}^m p_n$ and $\pi_2 = \pi_{n=m+1}^k p_n,$ if you subtract the two products the difference $d = |\pi_2 - \pi_1|$ will be prime if the difference is small enough (and maybe there were some other requirements).  
Ah. The article is by Thompson, American Mathematical Monthly, vol. 60 no. 3 (1953), A Method for Finding Primes. I don't have access to it. 
For example (only), $11\cdot7 - 2\cdot3\cdot5 = 47, $ which is evidently prime because it is not a product of any primes less than $11$, and $11\cdot13$ is already too big. This is the general idea. 
It too is impractical. 
A: You could always use a prime-generating polynomial. There exists a polynomial in $10$ variables such that the set of primes is precisely the positive values of the polynomial as the variables ranges through the non-negative integers. Working with the polynomial might be a bit troublesome though since it's degree is $\sim10^{45}$. Alternatively there is also a polynomial in $26$ (lucky we have that many alphabets) variables with the same properties given here
$$(k+2) (1 -
 [wz + h + j - q]^2 -
 [(gk + 2g + k + 1)(h + j) + h - z]^2 -
 [16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2]^2 - 
 [2n + p + q + z - e]^2 - 
[e^3(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 - 
 [n + l + v - y]^2 - 
 [(a^2 - 1)l^2 + 1 - m^2]^2 - 
[ai + k + 1 - l - i]^2 -
 [((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2]^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) $$
A: You could just use the sieve of Eratosthenes and get all of them.
Euclid proposed this method: Take any finite set of primes, multiply them, add $1$, and then (the hard part) factor the result.  It's easy to prove (and Euclid did prove) that all of the resulting primes fail to be in the set you started with.  Therefore, no matter how large a finite set of primes you start with, there are still more primes than that.
But this isn't really practical, because of "the hard part", factoring.
A: $$ n^2 + n+ 41 $$  gives a set of primes for 0 ≤ n < 40 .
This is called euler's prime generating polynomial.
Euler also told that $$ n^2 - n+ 41 $$ gives primes for n from 0 to 40.
Surprisingly the terms which result on substituting number's from 0 to 40 , gives numbers which differ by consecutive even term 2,4,6,8........ So this feature can be used to primes(off course only within this range) by starting from 41 and adding even terms to successive terms in prime number series .
Please refer 
http://en.wikipedia.org/wiki/Formula_for_primes#Prime_formulas_and_polynomial_functions
This is a method to get primes within this limit , despite the 6K+1 and 6K-1 method to get primes (but this also gives composite numbers at times like for eg. k=8 , 6k+1 gives 49 which is not prime ).
Refer http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html for more such polynomials and idea behind such polynomials .
