# Project Euler 27 - Quadratic Primes

Project Euler problem 27

I decided to try simple brute force, and it worked surprisingly quickly. How can this be optimized?

"""Considering quadratics of the form:
n^2 + an + b, where |a| < 1000 and |b| < 1000
Find the product of the coefficients, a and b,
for the quadratic expression that produces
the maximum number of primes for
consecutive values of n,
starting with n = 0."""

from timeit import default_timer as timer
import math
start = timer()

def isPrime(k): # checks if a number is prime
if k < 2: return False
elif k == 2: return True
elif k % 2 == 0: return False
else:
for x in range(3, int(math.sqrt(k)+1), 2):
if k % x == 0: return False

return True

longest = [0, 0, 0] # length, a, b
for a in range((alim * -1) + 1, alim):
for b in range(2, blim):
if isPrime(b):
count = 0
n = 0
while isPrime((n**2) + (a*n) + b):
count += 1
n += 1

if count > longest[0]:
longest = [count, a, b]

return longest

elapsed_time = (timer() - start) * 100 # s --> ms

print "Found %d and %d in %r ms." % (ans[1], ans[2], elapsed_time)


This is mostly quite good, but has some issues.

• The required answer to the Project Euler problem is not the values of $a$ and $b$, but their product. You could output that value rather than requiring another computation.

• Your prime test could be speeded up by first calculating a table of primes, then only checking for divisibility against that.

primes = [2, 3]

def extend_primes(upto):
"""Pre-extend the table of known primes"""
for candidate in range(primes[-1], upto + 1, 2):
if is_prime(candidate):
primes.append(candidate)

def is_prime(x):
"""Check whether "x" is a prime number"""
# Check for too small numbers
if x < primes[0]:
return False
# Calculate the largest possible divisor
max = int(math.sqrt(x))
# First, check against known primes
for prime in primes:
if prime > max:
return True
if x % prime == 0:
return False
# Then, lazily extend the table of primes as far as necessary
for candidate in range(prime[-1], max + 1, 2):
if is_prime(candidate):
primes.append(candidate)
if x % candidate == 0:
return False
return True


Whether this actually improves performance would have to be properly benchmarked.

• Your longest is an list. Instead, you probably wanted to use a tuple:

longest = (0, 0, 0)
...
if count > longest[0]:
longest = (count, a, b)
...


What is the difference? A list is a variable-length data structure where all entries should have the same type. In C, the rough equivalent would be an array. A tuple is a fixed-size data structure where each entry can have a different type. The C equivalent would be a struct.

However, I think it would be actually better to use named variables instead of indices:

longest_count = 0
longest_a = None
longest_b = None
...
if count > longest_count
longest_count = count
longest_a = a
longest_b = b
...
return longest_a, longest_b
...


This is longer, but more readable.

• Your code takes some nice shortcuts but fails to explain why you can take these shortcuts.

For example, you only test a $b$ if it's a prime. This follows from the $n = 0$ case where the expression can be reduced to $b$, which therefore has to be prime. This also allowed you to narrow the search space from $(-1000, 1000)$ to $[2, 1000)$. Just mention this in a comment instead of implying it.

If we pre-calculate a prime table, we could also iterate through those known primes instead of testing each number again and again:

extend_primes(blim)
for b in primes:
if b >= blim:
break
...

• Your n and count variables are absolutely equivalent. Keep n, discard count.

• Stylistic issues:

• Variables and functions etc. should use snake_case, not camelCase or some quiteunreadablemess. If possible, they should consist of proper words rather than abbreviations, except for very common abbreviations like maximum as max.

• alima_lim or a_max
• isPrimeis_prime
• longestPrimeQuadraticlongest_prime_quadratic (although this name doesn't convey very well what this function is doing)
• ansanswer, but returning a tuple and destructuring this is probably cleaner.
• Don't use one-line conditionals like if k < 2: return False. Instead, use all the space you need to make it as readable as possible:

if k < 2:
return True

• Put spaces around binary operators. math.sqrt(k)+1 becomes math.sqrt(k) + 1

• alim * -1 would usually be written with an unary minus: -alim.

@amon sums up all the points pretty well. Adding on that, a possible optimization would be to check if (a+b) is even after already checking if b is prime. This can be justified by the fact that at n = 1 the equation becomes:

12 + a(1) +b

which is:

a+b+1

Thus for a+b+1 to be a prime, a+b has to certainly be even, or in other words, also check if:

if a+b % 2 == 0:


Another optimization would be to store the last highest found value of n for a set of values of a and b. :

if count > longest[0]:
longest = [count, a, b]
max_solution = n-1


Now on the next test case values of a and b you could first check if the equation gives out a prime value for n = max_solution intead of starting from n = 0.