Project Euler 27
オイラーは以下の二次式を考案している: n^2 + n + 41. この式は, nを0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40のとき402 + 40 + 41 = 40(40 + 1) + 41となり41で割り切れる. また, n = 41のときは412 + 41 + 41であり明らかに41で割り切れる. 計算機を用いて, 二次式 n^2 - 79n + 1601という式が発見できた. これはn = 0 から 79 の連続する整数で素数を生成する. 係数の積は, -79 × 1601 で -126479である. さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値): n^2 + an + b n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ.
Mathematica
ans = 0; For[a = -999, a < 1000, a++, For[b = -999, b < 1000, b++, n = 1; While[PrimeQ[n^2 + a n + b], n++; ]; ans = Max[ans, n]; If[ans == n, Print[{a, b, ans}], {}] ] ]
大した工夫も面白い関数もありませんね・・・
PrimeQは便利なので、他の言語で参加している方も、それぞれ自分で作ると便利ですよ。
C/C++
#include <iostream> #include <deque> using namespace std; deque<bool> p; void calc_prime(const int); bool is_prime(int); int primeGenerateNum(int a, int b){ int num=0, n; for(int i=0 ; ; i++){ n = i*i + a*i + b; if(n <= 0) break; if(is_prime(n)) num++; else break; } return num; } int main(){ calc_prime(500000); int tmp=0; for(int i=-1000 ; i<1000 ; i++){ for(int j=-1000 ; j<1000 ; j++){ if(tmp < primeGenerateNum(i,j)){ tmp = primeGenerateNum(i,j); cout << i << " " << j << " " << i*j << endl; } } } int end; cin >> end; } /* maxまでの素数を計算する。 あらかじめ deque<bool> p; をグローバルで宣言しておいてね */ void calc_prime(const int max){ for(int i=0 ; i<max+1 ; i++){ p.push_back(true); } p[0] = false; p[1] = false; double myEnd = sqrt(double(max)); for(int i=2 ; i < myEnd ; i++){ for(int j=2 ; i*j<=max ; j++){ p[i*j] = false; } } cout << "Finish calculate primes 1 into " << max << endl; } // nが素数かどうか bool is_prime(int n){ return p[n]; }
Project Euler 35で作成したcalc_prime, is_primeを流用、超楽。