Quadratic Primes - Project Euler 27 Project Euler Problem 27


  Euler discovered the remarkable quadratic formula:
  
  \$n^2 + 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^2 + 40 + 41 =
&gt; 40(40 + 1) + 41\$ is divisible by \$41\$, and certainly when \$n = 41, 41^2 +
 41 + 41\$ is clearly divisible by \$41\$.
  
  The incredible formula \$n^2 − 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^2 + an + b\$, where \$|a| &lt; 1000\$ and \$|b| &lt; 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&lt;int&gt; primes = Primes(10000000);

    Func&lt;int,int,int,int&gt; f = (a,b,n) =&gt; n * n + a * n + b;

    int maxCount = int.MinValue;
    int x = 0;
    int y = 0;
    for(int a = -999;a &lt; 1000;a++)
    {
        for(int b = -999;b &lt; 1000;b++)
        {
            int count = 0;
            int n = 0;
            while(primes.Contains(f(a,b,n++))) count++;
            if(count &gt; maxCount)
            {
                maxCount = count;
                x = a;
                y = b;
            }
        }
    }

    Console.WriteLine("x * y = {0}",x * y);
}


static HashSet&lt;int&gt; Primes(int n)
{
    HashSet&lt;int&gt; primes = new HashSet&lt;int&gt;();
    BitArray a = new BitArray(n+1,true);

    for(int i = 2;i &lt;= Math.Sqrt(n);i++)
    {
        if(a[i])
        {
            for(int j = i * i;j &lt;= n;j += i)
            {
                a[j] = false;
            }
        }
    }

    for(int i = 2;i &lt; a.Length;i++)
    {
        if(a[i]) primes.Add(i);
    }
    return primes;
}


How can I improve this? Can you offer a more efficient implementation?
There is one relatively simple optimization you can do, for a start, and it will likely make a big difference...

If you analyze the equation:

n² + an + b, where |a| &lt; 1000 and |b| &lt; 1000


you need to solve it for where n² + an + b is prime.

The first n value to use is 0. 0² +a0 +b is b, thus, in order to process any values, it is clear that b needs to be a prime number (and not negative either...).

Thus, you should rearrange your loops, and your outer loop should be on the first k prime numbers in your set, where the k'th prime is &lt; 1000.

There are 168 primes less than 1000, so that will reduce your loops from 2000 'b' loops to just 168.

Similarly, when you loop on only those 168 primes, you are guaranteed that the n == 0 result is prime, and you only need to test on the n &gt; 0 condition.

Further, when n is 1,  the equation becomes:

1 + a + b = prime


or, since you have primes already from your sieve, you can significantly restrict the data-set by doing:

a = prime - b - 1


for primes in the range of b - 998 through to b + 1000 (which will keep a within the limits of -999 to +999). Note that there are no primes less than 2, and only a few hundred primes less than the 'worst case' (b ==999) + 1000

Only if you satisfy those two conditions would I consider even calling the prime function f(a,b,n++)