Project Euler で紹介されている問題27を解いてみました。素数を多く生成する2次多項式を求める問題を紹介します。
Project Euler 問題27（二次式の素数）
オイラーは、次の驚くべき二次式を発見した。
この式は、0 から連続する整数の値に対して40個の素数を生成することが分かった。しかし、
また、
次の式を考える。
ここで、
例
0 から始まる連続した値に対して、生成する素数の数が最大となる二次式の係数
解答例
素数か判定する関数は道具箱から持ってきました。注意としては、素数は、2より大きな自然数であることが前提となっています。これは、素因数分解の一意性を保たつためです。例えば、1 や負の整数を素数に加えると
など、同じ数に対して、複数の素因数分解ができてしまいます。これを避けるため、素数は 2 以上の自然数であることを前提としています。
係数
#include <stdio.h>
int is_prime(int n)
{
int answer = 1;
int i;
if (n == 1) {
answer = 0; /* 1 is not a prime number. */
}
for (i = 2; i * i <= n; ++i) {
if (n % i == 0) {
answer = 0;
break;
}
}
return answer;
}
int main(void)
{
int a, b, n;
int max_a, max_b, max_n;
int number;
max_a = 1;
max_b = 41;
max_n = 40;
for (a = -999; a <= 999; ++a) {
for (b = -1000; b <= 1000; ++b) {
n = 0;
number = n * n + a * n + b;
while ((number > 1)&&(is_prime(number) == 1)) {
++n;
number = n * n + a * n + b;
}
if (n > max_n) {
max_a = a;
max_b = b;
max_n = n;
}
}
}
printf("Problem027: %d\n", max_a * max_b);
printf("Problem027: n^2 + %d*n + %d (%d)\n", max_a, max_b, max_n);
return 0;
}実験
係数の条件を変更して、0 から連続する値に対して、最大個数の素数を生成する二次式を求めました。
| 条件 | 二次式 | 生成する素数の数 |
最後に
素数を生成する式を求めることは興味深い問題と考えられていました。二次式という簡単な式で、多くの素数を生成する式を見つけることができました。
引き続き、Project Euler の問題を紹介していきます。
