Project Euler 37
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3). 右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ. 注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
Mathematica
ans = {}; For[i = 10, i <= 1000000, i++, A = i; A2 = i; tmp = {i}; While[(A = FromDigits[Rest[IntegerDigits[A]]]) != 0, tmp = Append[tmp, A] ]; While[(A2 = FromDigits[Most[IntegerDigits[A2]]]) != 0, tmp = Append[tmp, A2] ]; If[MemberQ[PrimeQ[tmp], False] == False, ans = Append[ans, i]; {} ] ] ans
Restはリストの最初の要素だけを除去する関数、Mostはリストの最後の要素だけを除去する関数です。わざわざ独立した関数にしなくてもいいだろ・・・と思いますが、せっかくなので使いました。こういうことがどんどん積み重なってコードの可読性が・・・ううううう。
Mathematicaでない場合は素数の判定、PrimeQの関数をいかに高速化するかが重要になるでしょう。
C/C++
#include <iostream> #include <deque> using namespace std; deque<bool> p; /* 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; } } } // nが素数かどうか bool is_prime(int n){ return p[n]; } // xを各桁ごとにばらしてdequeに挿入する。 deque<int> integerDigits(int x){ deque<int> arr; while(x!=0){ arr.push_front(x%10); x/=10; } return arr; } int fromDigits(deque<int> arr){ int x=0; while(!arr.empty()){ x *= 10; x += arr[0]; arr.pop_front(); } return x; } int main(){ calc_prime(1000000); int k= 3797, sum=0; bool isTruncate=true; deque<int> karr; for(int k=11; k<=1000000 ; k+=2){ isTruncate = true; karr = integerDigits(k); while(isTruncate && !karr.empty()){ if(!is_prime(fromDigits(karr))) isTruncate=false; karr.pop_front(); } karr = integerDigits(k); karr.pop_back(); while(isTruncate && !karr.empty()){ if(!is_prime(fromDigits(karr))) isTruncate=false; karr.pop_back(); } if(isTruncate){ cout << k << endl; sum += k; } } cout << "Finish" << endl; cout << sum << endl; int end; cin >> end; }
11個あるというのだが、11個目が結構でかいので強敵かも。