4
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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.

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.