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();
}

Day 0

和世亮同学起了个早，步行到公司坐预订的Shuttle Express到了Tacoma机场，不顾天寒地冻到StarBucks要了杯Vanilla Bean当早餐。然后无聊地坐飞机飞到JFK机场，找到传说中的纽约地铁，穿了大半个纽约城，找到83街我们的旅馆。住的条件比想象的还要糟糕点，基本只有床，仅仅能睡睡觉罢了。纽约的地铁倒真是很方便的，2块钱哪里都能去，比起Seattle无车寸步难行好多了。

收拾完了，下坐到59街，在地铁口等到珊同学及其朋友，4个人去Todai吃了顿自助。世亮同学借了手机抓紧时间向雅琴同学汇报，然后商量好次日碰头地点，就闪回去休息了。

Day 1

早起，胡乱吃了点早餐，继续在59街和珊同学汇合。第一站是Rockefeller广场，有世界上最大的圣诞树，下边有一个溜冰场，无数浪漫电影在这里拍过。傻傻地留个影，继续逛。

下一站是St. Patrick教堂，其实是无意路过的。教堂高达100公尺，是纽约最大规模教堂，又是世界第11大教堂。它的外观是仿造德国奎尔论大教堂而建成的，经过38年的工程，1850年才完成的。教堂的高高耸立的双塔便成为第5大街的象征。教堂内部有精致的花纹玻璃窗和非常大的管风琴。每年3月17号St. Patrick's Day，爱尔兰裔美国人穿绿色服装到此聚集起来，并进行圣派特里克诞生庆祝活动。

找到一个NBA商场，非常大，貌似电视里经常看到。好多东西想买啊，不过太贵，转了圈，又在里边玩了会投篮就出来了。发现手感下降得严重啊，回国后要好好锻炼下。

然后地铁到World Trade Center遗址，被围起来了，盖新楼吧。也没什么看的，难以想象6年前的某天，此处是何等的惊心动魄，anyway "This Is A Special Place"。

Wall Street是下面一站，只是觉得高楼很多，跟上海差不多，然后三个人很傻的找了半天才找到金牛，必须要合影下了，anyway，大盘还是继续在跌，sign～

马不停蹄的又赶到唐人街，其实根本难以分辨这是在国内还是在纽约，熙熙攘攘的人群，叫卖着东西。只是觉得在这里生活也并不见得好到哪去，据珊同学讲很多人就只待在唐人街，都不到其他区去。Sign，觉得何必呢，背井离乡跑到一个陌生的国度……

继续转回到Wall Street附近，打算去看自由mm。不过不巧到了那里最后一班上岛邮轮已经没了，遂等渡轮（不上岛的），最后只能远远的看下自由mm。

晚上吃了顿火锅，还行，比Seattle的强多了。然后逛Macy和Victoria's Secret，世亮同学远程连线雅琴同学，终于确定了要买啥化妆品，我也买好香水，完成家里交代的任务。

继续步行至Time Square，在灯红酒绿的街头逛了逛，没啥感觉，回去睡觉。

Day 2

计划是上午逛Museum of Natural History，下午去United Nation。

不过没想到museum这么杀时间的。不过老美的museum做的真不错，也不收门票，donate下就行。

只是逛着逛着就忘了时间，于是匆匆忙忙的又奔赴UN。今天不知道啥日子，所有的国旗都没升，和国旗合下影的愿望也破灭了。干脆进去在外堂和安南的像合了个影就回来了。

奔赴传说中第五大道的apple专卖店。设计得倒是挺漂亮的，不过下午那个楼梯……忒难走了，这么狭窄……yy了很久，还是放弃MacBook的打算，不然又被人喊败家了……

人困马乏，坐地铁到珊同学的Columbia University，因为珊同学说她饭做的很好吃，要给我们露一手。在哥大校园转了下，真小啊，不过想想纽约的地皮这么贵，也正常吧，ZJG盖那么大我倒觉得浪费了。哥大旁边就是哈林去，全美最危险的地方，我们也没有进去转了……

然后，经过鉴定，珊同学的手艺还是不错的，不愧是衢州娜妮啊，给家乡人民长脸了～

Day 3

比较不顺，早上就开始下小雨了。冒着雨穿过Central Park到Metropolitan Museum of Art，结果人家周一不开门……

得，辗转到MoMA(The Museum of Modern Art)。MoMA藏有Vincent Van Gogh的名画The Starry Night，据说每天开馆闭馆都会播Don McLean的Vincent，我很喜欢的一首歌，可惜没赶上。里面还有Picasso的好多名画比如Les Demoiselles d'Avignon。逛来逛去就越发觉得自己像文盲，比如一幅作品吧，把一张白纸涂成全蓝，愣是没看出啥……让我想起公司我们34号楼也有个挂的画，就一张白纸-_-...

晚上看电影，新上映的Beowulf。3D画面挺炫，故事情节倒很简单，人类世界的大英雄，干掉了前国王和女妖生的孽种，结果自己又被女妖诱惑生了个孽龙，然后亲手把孽龙干掉，自己也挂了。学习smell同学05年在PKU的总结，“英雄难过美人关”啊……

Day 4

早起，挥别纽约，继续无聊地坐飞机回到Seattle，完。

11月1日终于迎来我的第一场NBA现场比赛，超音速在主场迎战太阳队。这是超音速新赛季的首个主场，太阳队新赛季的第一场比赛。

球赛是晚上7点开始，下午4时就向组里发了OOF的信，然后到公司旁边的公交车站等汽车。由于之前已经踩过点，所以这次找到钥匙球馆比较顺利，就是等车花了不少时间：坐了20分钟公交到西雅图市区，然后步行到球馆，中间还找了间不错的馆子吃了顿牛排，吃饱了才有力气看球啊，呵呵。

到达球馆是6点40左右，钥匙球馆这时候已经非常热闹了，虽然Allen和Lewis都离开了球队，看来大家对超音速新赛季还是很有热情的，因为有超新星Durant。

在门口留影，然后领了超音速的球迷服，黄色T恤，上面印有THE SUPES ARE BACK。有点心虚，呵呵，因为我是支持太阳队的。在球馆大厅走了半圈，找到了我们的113 section，终于进到球馆里面了。米果然没白花，那是相当的近啊，第一眼就看到两个熟悉的身影，Nash和Marion。Nash果然是MVP，赛前的训练相当认真，一丝不苟，罚球、变相突破、3P，看得忍不住想下场和他较量下了。

由于超音速下赛季可能要搬离西雅图，所以不少球迷都打出标语来挽留球队，类似“KEEP THE SONICS IN SEATTLE”，还有球迷打出“THIS CITY NEEDS THE SONICS”，不过怎么看都是托，一句话分三段首字母连起来是TNT。-_-

正式的开球等到了7点45，介绍完客场球队后，全场关灯一片漆黑，开始介绍主场球员。电视上已经见了多次了，但现场还是有不一样的感觉，很酷，Durant最后登场，引来主场球迷一片欢呼。然后再次熄灯，啦啦队举美国国旗入场，全场起立，演艺界人士（不知道谁）唱美国国歌。接下来比赛正式开始。

上半场是超音速攻我们这边的篮筐。由于过去几个赛季超音速成绩实在不好，也基本没有电视台直播，所以主力阵容里我知道的也就只有Durant。太阳这边星光灿烂，MSN组合、Bell加上新加盟的Hill。虽然实力上稍逊一筹，但超音速球员都打得格外卖力，毕竟第一个主场，要对得起观众啊。尤其是Durant，表现格外抢眼，完全不像一个19岁的新秀，几次投篮、突破都很有感觉，像年轻时候的TMac，一次抢断后快速突破扣篮更是把钥匙球馆的气氛拉倒顶点，只是进攻的稳定性和投篮时机的选择还需要磨练。反观太阳这边，也是强队风范，虽然看上去没什么，但是始终让超音速拉不开比分。Stoudemire的两次爆扣给人留下了很深的印象，真的很难想象，隔着一个人就这么蹦起来扣进去了，小霸王，并非浪得虚名。而Nash，就像一个不知疲倦的发动机一样，为球队送出助攻。但是客观讲，Nash还没有达到他的最佳竞技状态，年龄又增大了加上刚开季的原因吧，上半场就出现了几次失误，进攻效率也一般，还没有让我们看到那个无所不能的Nash。整个上半场都打得比较胶着，半场结束前超音速扔了一个超远3P，竟然进了，以58:55领先结束半场。Durant半场就得了18分，不愧是榜眼啊。

撇开比赛不说，NBA真是一个运转相当良好的商业机器，即使在中间暂停休息的时候也穿插了很多活动：啦啦队的表演、抽奖、短片，总之不会让观众闲着，保持着很high的情绪。

进入到第三节，超音速发力，一度领先到了10分左右了，但是被太阳的Banks连续3记3P一下子又追回来了。僵局持续到第四节，太阳终于发力了，把比分反超。这时候，太阳开始显现出强队的风范，打得很稳，用快攻和3P来冲击超音速。超音速则感觉进攻办法不多了，大多靠个人单兵作战。Nash在最后阶段起到了定海神针的作用，一次次投篮命中加助攻不断打压超音速反超的企图。而Durant，被球队寄予厚望，可惜却在最后阶段多次失误。虽然他的1个3P几乎将比分迫近，但在一次失误被抢断，Stoudemier暴扣以后，彻底宣告主队反超无望，大半球迷也提前离场。

最后MSN组合都拿到两双，算是一个不错的开局。而超音速在面对强队时也发挥出了自己应有的水平，祝福这支年轻的球队后面越大越好。Durant，以27分结束了自己的主场debut，算是交上了一份不错的答卷，看好他以后能成为联盟顶级的小前锋。

最后，应学俊所托，到礼品店买球服，可惜他的首选Bell和Stoudemier都没有，买了Durant的，不过相信有今天的表现，他也应该满意的。