In Problem 146 of Project Euler we are working with primes again, and some quite big ones even. The problem reads

The smallest positive integernfor which the numbersn^{2}+1,n^{2}+3,n^{2}+7,n^{2}+9,n^{2}+13, andn^{2}+27 are consecutive primes is 10. The sum of all such integersnbelow one-million is 1242490.

What is the sum of all such integersnbelow 150 million?

At first I thought I could just make a sieve up to 150 million and then check if the numbers were contained in that. However, rereading the problem I realized I was completely wrong. So in a pure brute force solution we would need to check 150 million values of n and up to 13 numbers for each, since we both need to check that the given numbers are prime. But also that the odd numbers inbetween are not prime. So potentially we have to check 1950 million numbers for primality, which is a moderately expensive operation. Continue reading →