Hi, I tried doing Project Euler #27 today, which asks the following:
Euler published the remarkable quadratic formula:
n² + 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² + 41 + 41 is clearly divisible by 41.
Using computers, the incredible formula n² − 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² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4Find 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.
So, I did my thinking and came up with the following code in a few minutes:
#include <iostream>
using namespace std;
int* sieve(int i)
{
bool* primes = new bool[i];
int* primelist = new int[i];
primes[0] = false;
primes[1] = false;
for (int j = 2; j < i; j++)
primes[j] = true;
for (int j = 2; j * j < i; j++)
{
if (primes[j])
{
for (int k = j; k*j < i; k++)
primes[k*j] = false;
}
}
for (int k = 2; k < i; k++)
{
if (primes[k])
primelist[k] = k;
}
return primelist;
}
bool isPrime(int check)
{
int* primes = sieve(1000);
for (int i = 0; i < 1000; i++)
{
if (check == primes[i])
return true;
}
return false;
}
int main()
{
int* primes = sieve(1000);
int max_co = 0;
int max_co_sec = 0;
int index = 2;
int max = 0;
int x;
for (int a = -999; a < 1000; a++)
{
for (int b = -999; b < 1000; b = primes[index++])
{
x = 0;
while (isPrime(x*x+a*x+b))
x++;
if (x > max)
{
max = x;
max_co = a;
max_co_sec = b;
}
}
}
cout << max_co * max_co_sec << endl;
return 0;
}What I did:
Function sieve() returns an array of prime numbers using the sieve of eratosthenes. This part is OK. I validated the function by generating random ranges of prime numbers and using brute-force to check them. It works.
Next, in the main(), there are two loops for checking combinations of n*n+a*n+b. isPrime() goes over the generated primes array to see if the number exists anywhere in it. If it does, then it is a prime.
This is basically what my program does.. Problem is, that I'm getting the wrong output. What I'm getting is something like -75913. The correct answer is something like -51318.
What am I doing wrong here? And, yes, I know there are many design flaws. Please point out as much as you can, as I want to improve my habits.
Thanks for reading :D
