HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Quadratic Primes

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
quadraticprimesstackoverflow

Problem

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  all_numbers = new HashSet();
    public HashSet list_of_primes = new HashSet();
    public HashSet list_of_nonprimes = new HashSet();

    public Primes(int n)
    {
        all_numbers = new HashSet(Enumerable.Range(1, n));
        for (int i = 2; i (all_numbers.Except(list_of_nonprimes));
    }

}

Solution

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:

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

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

-
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  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;
    }

Code Snippets

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;
    }

Context

StackExchange Code Review Q#25227, answer score: 2

Revisions (0)

No revisions yet.