4
\$\begingroup\$

This is one of the slightly trickier Project Euler Questions I have seen (Question 27)

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.

Here is my code let me know if this is good coding practice. Thanks.

class QuadraticPrimes
{
    static void Main(string[] args)
    {
        int max = 1000;
        Primes primes = new Primes(max);
        int n = 0;
        int m = 0;
        int a = -999;
        int b = -999;

        for (int i = -999; i < 1000; i++)
        {
            for (int j = -999; j < 1000; j++)
            {
                while (true)
                {
                    m++;
                    if(primes.list_of_primes.Contains(quadratic(i, j, m)) == false)
                        break;
                }

                if (n < m)
                {
                    n = m;
                    a = i;
                    b = j;
                }
                m = 0;
            }
        }



        Console.WriteLine("a:" + a + ", b:" + b + ", n:"+n);
        Console.ReadLine();

    }

    public static int quadratic(int a, int b, int n)
    {
        return n*n + a*n + b;
    }
}


class Primes
{
    public HashSet<int> all_numbers = new HashSet<int>();
    public HashSet<int> list_of_primes = new HashSet<int>();
    public HashSet<int> list_of_nonprimes = new HashSet<int>();


    public Primes(int n)
    {
        all_numbers = new HashSet<int>(Enumerable.Range(1, n));
        for (int i = 2; i < Math.Sqrt(n) + 1; i++)
        {
            for (int j = 3; j <= n / i; j++)
                list_of_nonprimes.Add(i * j);
        }
        list_of_primes = new HashSet<int>(all_numbers.Except(list_of_nonprimes));
    }

}
\$\endgroup\$
2
\$\begingroup\$

Pre-computing a large list containing numbers you may or may not use isn't always a good idea. I tested it and it turns out to be much slower.


Things I would change about your code:

  1. I'd remove the classes, this is a trivial problem that can be solved with a few methods, follow the KISS principle and keep it simple.

  2. I'm not a fan of your while loop. It can be recreated as:
    int m = 0;
    while (primes.list_of_primes.Contains(quadratic(i, j, m++));

    Which avoids break;. While we're at it, in my version I use a for loop so that the m++ is cleaner and we are sure it's happening after the fact.

  3. You don't need to initialize a or b to -999, it makes things messier and doesn't provide any value.


Here's how I would do it, breaking things apart into methods with their own purposes. I also used a slightly more efficient IsPrime, but it's nothing special.

    static int FindMaxCoeff()
    {
        int maxConsec = 0;
        int maxCoeff = 0;
        for (int a = -999; a < 1000; a++)
        {
            for (int b = -999; b < 1000; b++)
            {
                int currentConsec = FindMaxConsecutive(a, b);
                if (currentConsec > maxConsec)
                {
                    maxConsec = currentConsec;
                    maxCoeff = a * b;
                }
            }
        }

        return maxCoeff;
    }

    static int FindMaxConsecutive(int a, int b)
    {
        int n = 0;

        for (n = 0; IsPrime(n * n + a * n + b); n++) ;

        return n;
    }

    static bool IsPrime(int n)
    {
        n = Math.Abs(n);
        if (n == 1 || n == 2 || n == 3)
        {
            return true;
        }

        if (n % 2 == 0 || n % 3 == 0)
        {
            return false;
        }

        for (int x = 6; x - 1 <= Math.Sqrt(n); x += 6)
        {
            if (n % (x - 1) == 0 || n % (x + 1) == 0)
            {
                return false;
            }
        }

        return true;
    }
\$\endgroup\$
  • \$\begingroup\$ Keep in mind there are many math tricks to optimize this solution, but they aren't strictly coding best practices. \$\endgroup\$ – Jean-Bernard Pellerin Apr 18 '13 at 23:17
  • \$\begingroup\$ Thanks for your solution, however I have a question about efficiency. You call the line for (n = 0; IsPrime(n * n + a * n + b); n++) ; meaning that you are going through your prime checking algorithm for the number n * n + a * n + b for each pair (a,b), n times (depending on how many consecutive primes occur. Whereas if you just create a list you avoid repeatedly computing the values. Unless I am unaware of some sort of efficiency work done by the virtual machine for the method bool IsPrime(int n) \$\endgroup\$ – phcoding Apr 19 '13 at 0:03
  • \$\begingroup\$ The work done to calculate IsPrime the necessary amount of times is less than the work required to create the list and then access it repeatedly. Try it out yourself with the Stopwatch class. \$\endgroup\$ – Jean-Bernard Pellerin Apr 19 '13 at 2:37
  • \$\begingroup\$ Surely it depends on the size of your list? I set max = 1000000 but max = 1000 would have worked perfectly too (changed code to reflect this). I didn't time it but it gave the result in an instant. \$\endgroup\$ – phcoding Apr 19 '13 at 2:59
  • \$\begingroup\$ Try it out yourself pastebin.com/TRPxKcUq \$\endgroup\$ – Jean-Bernard Pellerin Apr 19 '13 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.