Finding consecutive primes matching p, p + 4, p + 6, p + 10, p + 12, p + 16 Someone asked about this question on the main StackOverflow. The full question is:


  Given a value N, find p such that all of [p, p + 4, p + 6, p + 10, p + 12, p + 16] are prime. 
  
  
  The sum of [p, p + 4, p + 6, p + 10, p + 12, p + 16] should be at least N.
  


My thinking is:


Sieve all primes under N
Ignore primes below (N-48)/6
Create consecutive slices of length 6 for the remaining primes.
Check if the slice matches the pattern.


Here's my solution. I'd appreciate some feedback. 

from itertools import dropwhile, islice
def get_solutions(n):
    grid = [None for _ in range(n+1)]
    i = 2
    while i &lt; n+1:
        if grid[i] is None:
            grid[i] = True
            for p in range(2*i, n+1, i):
                grid[p] = False
        else:
            i += 1
    sieve = (index for index, b in enumerate(grid) if b)
    min_value = (n - 48) / 6
    reduced_sieve = dropwhile(lambda v: v &lt; min_value, sieve)
    reference_slice = list(islice(reduced_sieve, 6))
    while True:
        try:
            ref = reference_slice[0]
            differences = [v - ref for v in reference_slice[1:]]
            if differences == [4, 6, 10, 12, 16]:
                yield reference_slice
            reference_slice = reference_slice[1:] + [next(reduced_sieve)]
        except StopIteration:
            break


n = 2000000

print(next(get_solutions(n)))

# or for all solutions
for solution in get_solutions(n):
    print(solution)
Overall, good first question!
The first obvious improvement is to factor out the code that generates the primes

def prime_sieve(n):
    grid = [None for _ in range(n+1)]
    i = 2
    while i &lt; n+1:
        if grid[i] is None:
            grid[i] = True
            for p in range(i*i, n+1, i):
                grid[p] = False
        else:
            i += 1
    return (index for index, b in enumerate(grid) if b)


Note that for p in range(i*i, n+1, i): starts later than the for p in range(2*i, n+1, i): which you used. This is safe because anything less than the current prime squared will have already been crossed out. This difference alone makes the code about 2x faster for n = 4000000.

By separating the sieve, it makes things like profiling much easier, and you can see that most of the time this method takes is still in the sieve. Using some tricks from Find primes using Sieve of Eratosthenes with Python, we can focus our efforts on speeding this part up.

def prime_sieve(n):
    is_prime = [False] * 2 + [True] * (n - 1) 
    for i in range(int(n**0.5 + 1.5)): # stop at ``sqrt(limit)``
        if is_prime[i]:
            is_prime[i*i::i] = [False] * ((n - i*i)//i + 1)
    return (i for i, prime in enumerate(is_prime) if prime)


This prime sieve works pretty similarly, but is shorter, and about 4x faster. If that isn't enough, numpy and https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188 can come to the rescue with this beauty which is another 12x faster.

import numpy
def prime_sieve(n):
    """ Input n&gt;=6, Returns a array of primes, 2 &lt;= p &lt; n """
    sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k//3     ::2*k] = False
            sieve[k*(k-2*(i&amp;1)+4)//3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]


At this point, further speedup would need to come from fancy number theory, but I'll leave that for someone else.