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個目が結構でかいので強敵かも。