Project Euler 27 - Quadratic Primes

Question

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 longestPrimeQuadratic(alim, blim):
 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
ans = longestPrimeQuadratic(1000, 1000)
elapsed_time = (timer() - start) * 100 # s --> ms
print "Found %d and %d in %r ms." % (ans[1], ans[2], elapsed_time)

Answer 1

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)
  ...
  _, a, b = longestQuadraticPrime(...)
  

  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
  ...
  a, b = longestQuadraticPrime(...)
  

  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.

    • alim → a_lim or a_max
    • isPrime → is_prime
    • longestPrimeQuadratic → longest_prime_quadratic (although this name doesn't convey very well what this function is doing)
    • ans → answer, 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.

Answer 2

@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:

1² + 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.