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 =
> 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| < 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 primes = Primes(10000000);

    Func f = (a,b,n) => n * n + a * n + b;

    int maxCount = int.MinValue;
    int x = 0;
    int y = 0;
    for(int a = -999;a  maxCount)
            {
                maxCount = count;
                x = a;
                y = b;
            }
        }
    }

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

static HashSet Primes(int n)
{
    HashSet primes = new HashSet();
    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? 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| < 1000 and |b| < 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 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++)`

StackExchange Code Review Q#67857, answer score: 7