Quadratic Primes - Project Euler 27

Question

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<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? Can you offer a more efficient implementation?

Why do you think you have to check values smaller than 10^7 only? If you ask for a value larger than 10^7 if it is a prime you will get the answer "no" even if it is prime. You should check if the value is smaller 10^7 otherwise you should do some appropriate action. You can print a message. — miracle173
– miracle173, Commented Oct 25, 2014 at 3:18
@miracle173 0.5 seconds, mostly because this line: HashSet<int> primes = Primes(10000000); — Rezo Megrelidze
– Rezo Megrelidze, Commented Oct 25, 2014 at 11:10
@miracle173 I did some experiments and Primes(100000) still works. Now it only runs for 0.156 seconds. — Rezo Megrelidze
– Rezo Megrelidze, Commented Oct 25, 2014 at 11:13

rolfl · Accepted Answer · 2014-10-24 20:48:01Z

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 < 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 > 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++)

user33306 · Accepted Answer · 2014-10-25 02:57:03Z

Another fairly major optimization in your Sieve algorithm, is do away with the hashset. If the index of the bitarray is true that number is prime. Also on a more minor vein, since 2 is the most unique prime, being even, if you loop through all the even numbers first, this greatly reduces the inner loop for the odd numbers since you only need to step the odd multiples:

static BitArray Primes(int n)
{
    BitArray a = new BitArray(n + 1, true);
    int limit = (int)Math.Sqrt(n);
    a[0] = false;
    a[1] = false;
    for (int i = 4; i <= limit; i += 2)
    {
        a[i] = false;
    }
    for (int i = 3; i <= limit; i += 2)
    {
        if (a[i])
        {
            int step = i * 2;
            for (int j = i * i; j <= n; j += step)
            {
                a[j] = false;
            }
        }
    }
    return a;
}

Maybe my conversion to Swift wasn't complete, but it seems as though using a limit of sqrt(n) effectively cuts out a large number of confirmed prime number. — Greg Combs
– Greg Combs, Commented Aug 22, 2015 at 19:25

Stack Exchange Network

Quadratic Primes - Project Euler 27

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Quadratic Primes - Project Euler 27

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions