Padlock / haru__q
問題
projecteuler.net
n2 + an + b (|a| < 1000 , |b| ≦ 1000)
上式にn=0,1,2…と入力し、最も長く連続して素数が出てくるaとbの積を求めよ。
もっとa,bの範囲を狭めたい
まずn=0の場合を考えると、
02 + a×0 + b = b
なので、bは素数じゃないといけない。
次にn=1の場合を考えると、
12 + a + b = a + b + 1
となる。
n=0の場合からbは素数だとわかってるので、b+1は偶数になる。
a+b+1が素数になるとすると素数は奇数なので、偶数＋奇数＝奇数からaは奇数でないといけない。
以上の二つから分かったのは、
(1) bは1000以下の素数
(1-1) よってbが0やマイナスはありえない
(2) |a|は1000未満の奇数
後はa,b総当たりで。
コード
using System.Collections.Generic;
using System.Diagnostics;
namespace Problem27
{
class Program
{
static void Main(string[] args)
{
int[] p = CreatePrimeArray(1000);
int maxN = 0;
int maxPd = 0;
for (int pi = 0; pi < p.Length; pi++)
{
int b = p[pi];
for (int a = 1; a < 1000; a += 2)
{
int tmp = QuadraticFormula(a, b);
if (maxN < tmp)
{
maxN = tmp;
maxPd = a * b;
}
tmp = QuadraticFormula(-a, b);
if (maxN < tmp)
{
maxN = tmp;
maxPd = -a * b;
}
}
}
Debug.WriteLine(maxPd);
}
<summary>
</summary>
static int QuadraticFormula(int a, int b)
{
int n = 0;
int p = 0;
while (true)
{
p = n * n + a * n + b;
if (IsPrime(p) == true)
{
n++;
}
else
{
break;
}
}
return n;
}
<summary>
</summary>
static int[] CreatePrimeArray(int max)
{
List<int> p = new List<int>();
for (int i = 0; i <= max; i++)
{
p.Add(i);
}
for (int i = 2; i <= max / 2; i++)
{
if (p[i] != 0)
{
for (int j = 2; p[i] * j <= max; j++)
{
p[i * j] = 0;
}
}
}
p.RemoveAll(obj => obj == 0);
return p.ToArray();
}
<summary>
</summary>
static bool IsPrime(int n)
{
if (n <= 0) return false;
int hn = n / 2;
if (n % 2 == 0) return false;
for (int i = 3; i <= hn; i += 2)
{
if (n % i == 0) return false;
}
return true;
}
}
}
答え
-59231
もっとaの範囲狭めたりできないかなぁ。
