Find the sum of all eleven primes that are both truncatable from left to right and right to left.

DFS搜即可，但是其实搜之前是不确定所有的值一定在Int32的范围内，所以先是用long long 来判断（当然如果有值超出了long long的范围就得用另外的做法了）。从左往右搜，所有的值都只可能由2、3、5、7之一开始，后面的值可以跟1、3、7、9 （其他的数都会制造出合数）。然后一边搜一边判断就可以了。

/**
 * 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 <iostream>
#include <sstream>
#include <set>
#include <cmath>
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();
}

Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

数据量不是很大（one million以下），暴力做即可。一点小trick就是偶数的二进制表示肯定是类似于1...0，所以必然不是对称的，可以略去。

/**
 * Problem: Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.
 * Algorithm: Brute Force
 * Author: daiwb
 * Date: 2008/08/31
 */

#include <iostream>
#include <sstream>
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;

bool isPal(string str) {
  int len = str.length();
  REP(i,len >> 1) {
    if (str[i] != str[len - 1 - i]) return false;
  }
  return true;
}

bool isPalDec(int val) {
  stringstream ss;
  ss << val;
  string str;
  ss >> str;
  return isPal(str);
}

bool isPalBin(int val) {
  string str = "";
  do {
    str += char((val & 1) + '0');
    val >>= 1;
  } while (val != 0);
  return isPal(str);
}

void run() {
  int res = 0;
  for (int i = 1; i < 1000000; i += 2) {
    if (isPalDec(i) && isPalBin(i)) res += i;
  }
  cout << res << endl;
}

int main() {
  run();
}

How many circular primes are there below one million?

小于one million的数实际上只有6位，而且考虑到大于9的circular prime number只可能包含1、3、7、9 （如果包含0、2、4、5、6、8那么循环过后就会被2或者5整除）。简单的做法就是判断出one million以内所有的数是否为素数（很快，都不用用+2，+4筛法），然后用dfs搜索所有1、3、7、9组成的数加以判断即可。

/**
 * Problem: How many circular primes are there below one million?
 * Algorithm: DFS
 * Author: daiwb
 * Date: 2008/08/31
 */

#include <iostream>
#include <sstream>
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 plist[80000], pcount = 0;
int mm[1000005];

int prime(int n){
  int i;
  if ((n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))
    return 0;
  for (i=0;plist[i]*plist[i]<=n;i++)
    if (!(n%plist[i]))
      return 0;
  return n>1;
}

void initprime(){
  memset(mm, 0, sizeof(mm));
  int i;
  mm[2] = 1;
  for (plist[pcount++]=2,i=3;i<1000000;i++)
    if (prime(i)) {
      plist[pcount++]=i;
      mm[i] = 1;
    }
}

int res, len;
int num[4] = {1, 3, 7, 9};

bool isCircularPrime(string str) {
  REP(i,len) {
    stringstream ss;
    ss << str;
    int val;
    ss >> val;
    if (mm[val] == 0) return false;
    str = str.substr(1) + str[0];
  }
  return true;
}

void dfs(int idx, string str) {
  if (idx == len) {
    if (isCircularPrime(str)) {
      ++res;
      cout << str << endl;
    }
    return;
  }

  REP(i,4) {
    dfs(idx + 1, str + char(num[i] + '0'));
  }
}

void run() {
  res = 0;

  // 1-9
  res = 4;

  for (len = 2; len <= 6; ++len) {
    dfs(0, "");
  }

  cout << res << endl;
}

int main() {
  initprime();
  run();
}