Project Euler Problem #27

February 14, 2010

Read the details of the problem here

Summary

Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Solution

I used a straightforward approach to this problem. I assumed that b had to be positive and that both |a| and |b| had to be prime numbers themselves to reduce the chance of b being a multiple of a so I used a sieve to generate the numbers and worked from that.

def isPrime = new boolean[12000]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..<(int)Math.sqrt(isPrime.size())) {
    if (!isPrime[i]) continue
    def j = i + i
    while (j < isPrime.size()) {
        isPrime[j] = false
        j += i
    }
}

def ( answer, maxlen ) = [ 0, 0 ]

for (a in -999..<1000) {
    if (!isPrime[Math.abs(a)]) continue
    for (b in 1..<1000) {
        if (!isPrime[b]) continue
        def n = 0
        while (isPrime[ (n * n) + (a * n) + b ]) {
            n++
        }
        if (n > maxlen)
            (maxlen, answer) = [ n, a * b ]
    }
}

This runs in 0.76 seconds with the creation of the sieve taking 0.54 seconds (68%). Rather than generating lists of primes and working from that I just used the array directly as performance is generally better like that (though in this case it probably wouldn’t have mattered). Selection of the upper bound of the prime sieve was initially larger than the 12,000 shown in order to prevent out-of-bound exceptions.

Conclusion

I didn’t really use any specific Groovy feature here apart from multiple assignment in a few places and in the for-loop syntax. Performance was completely adequate for the scope of this problem.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: