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|  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)

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

-
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`.

StackExchange Code Review Q#47055, answer score: 3