/** * Problem: Find the sum of all eleven primes that are both truncatable from left to right and right to left. * Algorithm: DFS * Author: daiwb * Date: 2008/08/31 */ #include #include #include #include using namespace std; #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<=(b);++i) typedef long long LL; int res; int num[4] = {1, 3, 7, 9}; int string2int(string str) { stringstream ss; ss << str; int res; ss >> res; return res; } bool isprime(int val) { if (val == 2 || val == 3 || val == 5 || val == 7) return true; if (val == 1) return false; int mid = (int)sqrt(val + 0.5); if ((val & 1) == 0) return false; for (int i = 3; i <= mid; i += 2) { if ((val % i) == 0) return false; } return true; } bool isok(string str) { if (str.length() == 1) return false; REP(len,str.length()) { string s = str.substr(len); if (!isprime(string2int(s))) return false; s = str.substr(0, len + 1); if (!isprime(string2int(s))) return false; } return true; } void dfs(string str) { stringstream ss; ss << str; int val; ss >> val; if (!isprime(val)) return; if (isok(str)) { res += val; } REP(i,4) dfs(str + char(num[i] + '0')); } void run() { res = 0; dfs("2"); dfs("3"); dfs("5"); dfs("7"); cout << res << endl; } int main() { run(); }