patterncsharpMinor
Quadratic Primes
Viewed 0 times
quadraticprimesstackoverflow
Problem
This is one of the slightly trickier Project Euler Questions I have seen (Question 27)
Here is my code let me know if this is good coding practice. Thanks.
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:
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
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.
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.