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

Problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
Using computers, the incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.
Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

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.

Solution (in Ruby)

Normally we would want to run through 1000 numbers in the outer loop and 1000 numbers in the inner loop to attack this problem. But we can significantly reduce that by just running 168 x 168 times by calculating the number of primes below 1000 first. This would reduce our running time. The rest of the solution is an as-is implementation of the problem statement.

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end

max_primes = []; a_s = []; b_s = []
INFINITY = 1.0/0.0

primes_upto_1000 = []
1.upto(999) do |each_num|
  primes_upto_1000 << each_num if is_prime(each_num)
end

primes_upto_1000.each do |a|
  primes_upto_1000.each do |b|
    each_prime = 0
    0.upto(INFINITY) do |n|
      break unless is_prime(n**2 - a*n + b)
      each_prime+=1 
    end
    max_primes<<< -a ; b_s << b
  end
end

puts "Product of a and b is #{a_s[max_primes.index(max_primes.max)] * b_s[max_primes.index(max_primes.max)]}" 

Hover here to see the solution

Cheers!!
Bragaadeesh.