Let k≥1 be an integer, and let (f₁(x), ..., f_k(x)) be k admissible linear polynomials over the integers with positive leading coefficients. We present two algorithms for finding all positive integers x where max(f_i(x))≤n and all the f_i(x) are primes. So finding twin primes, prime k-tuples, and Cunningham chains are special cases covered by our algorithms.

Our first algorithm takes O( nk / (log log n)^k ) arithmetic operations using O( k sqrt(n) ) space. It is a generalization of the Atkin-Bernstein sieve.

Our second algorithm takes a factor of log log n more time, but only needs O(n^c) space for 0<c<1/2, for k>2. It is based on the sieve of Eratosthenes and not the Atkin-Bernstein sieve. The proof of the running time, but not correctness, relies on an unproven conjecture. This conjecture is not needed if k>6.

We showed the second algorithm is useful in practice by setting some new computational records, including extending the table of known prime quadruplets and finding some new Cunningham chains.