Return to Revisions

Project Euler Problem 27

Euler discovered the remarkable quadratic formula:

n2 + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 +たす 40 +たす 41 =わ 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 412 + 41 + 41 is clearly divisible by 41.

The incredible formula n2 − 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:

n2 + 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.

My Implementation:

I used Sieve of Eratosthenes for finding primes. I also used a HashSet for fast searching.

static void Main()
{
 HashSet<int> primes = Primes(10000000);
 
 Func<int,int,int,int> f = (a,b,n) => n * n + a * n + b;
 
 int maxCount = int.MinValue;
 int x = 0;
 int y = 0;
 for(int a = -999;a < 1000;a++)
 {
 for(int b = -999;b < 1000;b++)
 {
 int count = 0;
 int n = 0;
 while(primes.Contains(f(a,b,n++))) count++;
 if(count > maxCount)
 {
 maxCount = count;
 x = a;
 y = b;
 }
 }
 }
 
 Console.WriteLine("x * y = {0}",x * y);
}
static HashSet<int> Primes(int n)
{
 HashSet<int> primes = new HashSet<int>();
 BitArray a = new BitArray(n+1,true);
 
 for(int i = 2;i <= Math.Sqrt(n);i++)
 {
 if(a[i])
 {
 for(int j = i * i;j <= n;j += i)
 {
 a[j] = false;
 }
 }
 }
 
 for(int i = 2;i < a.Length;i++)
 {
 if(a[i]) primes.Add(i);
 }
 return primes;
}

How can i improve this, maybe you can offer a more efficient implementation?