問題27

プロジェクトオイラーの27問目。オイラーが見つけた、素数を生み出す2次式に関連した問題。

n=0, 1, 2, .. について、最も多くの素数を生成するようなaとbの積を考える。

(◎-ω-)｡ｏ○ (思案中)

• 全部調べるのはアホなので、ちょっと数式を観察してみる
• n=0からだから、bは素数のはず
• aも1か素数とかないかな‥無さそうだな‥(´・ω・｀)
• bと2次式の結果のために素数配列b、cを作ろうかな(エラトステネスの篩が爆速)
• 結果の配列数はくらい用意しとけば良いかな

Cで実装

#include <stdio.h>

/*素数配列: 番号が素数だったら0が入ってる*/
int b[1001] = {1, 1};       /*bは素数*/
int c[2001000] = {1, 1};    /*和の素数判定用*/
int len = 0; int pro; int s; int t;

void prime(void){       /*素数は0*/
    for(int i=2; i<=1000; i++){
        for(int j=i+i; j<=1000; j+=i){
            b[j]=1;
        }
    }
    for(int i=2; i<2001000; i++){
        for(int j=i+i; j<2001000; j+=i){
            c[j]=1;
        }
    }
}

int isprime(int x, int y, int n){   /*素数なら0*/
    if(n*n+x*n+y<0) return 1;       /*負だったら1(終了)*/
    return c[n*n+x*n+y];
}

void find(void){
    for(int i=0; i<1000; i++){
        for(int j=2; j<=1000; j++){
            int m=0; int n=0;
            if(b[j]==0){
                int x=i; int y=j;   /*+-で4通りの計算*/
                while(!isprime(i, j, m)) m++;
                while(!isprime(-i, j, n)) n++;
                if(n>m){m=n; x=-i;} n=0;
                while(!isprime(i, -j, n)) n++;
                if(n>m){m=n; y=-j;} n=0;
                while(!isprime(-i, -j, n)) n++;
                if(n>m){m=n; x=-i; y=-j;} n=0;
                if(m>len){len=m; pro=x*y; s=x; t=y;}
            }
        }
    }
}

int main(void){
    printf("--Quadratic primes--\n");
    prime(); find();
    printf("length: %d, %d*%d = %d.\n", len, s, t, pro);
    return 0;
}

お行儀が悪すぎる？ほっとけ！！！！

結果

$ gcc -O2 -Wall -std=c99 -o 27 27.c
$ ./27
--Quadratic primes--
length: 71, -61*971 = -59231.

が連続で71個()の素数を生成するらしい(｀・ω・´)

お時間もそこまでかからず、よかったよかった

real    0m0.254s
user    0m0.000s
sys     0m0.015s