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| &lt; 1000 and |b| &lt; 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 &lt; 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 &gt; longest[0]:
                    longest = [count, a, b]

    return longest

ans = longestPrimeQuadratic(1000, 1000)

elapsed_time = (timer() - start) * 100 # s --&gt; 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 &lt; 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 &gt; 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 &gt; 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 &gt; 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 &gt;= 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 &lt; 2: return False. Instead, use all the space you need to make it as readable as possible:

if k &lt; 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.