プロジェクトオイラー問35

Problem 35 「巡回素数」 †

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.

100万未満の巡回素数はいくつあるか?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2035

解法

素朴な解法としては。

まずエラトステネスの篩で素数の判定テーブルを作ります。

後は素数を全部調べます。

素数なら全部の巡回で判定テーブルでＯＫがでるかを調べればよいですね

巡回判定のコストは小さいので２を含む素数は判定しないなどを特にする必要はないでしょう。

２を含むかチェックするコストとそんなに大差は出ないはずです。

Ｃ++なら早いのでこれでも十分です。

Ｐｒｏｌｏｇなら２桁以上の巡回素数はどの桁にも1,3,7,9以外の数字が出てこないことを利用して解きます。
探索範囲を狭めて解きます。

#include<stdio.h>
#include<string.h>
#include<math.h>
const int LIMIT=1000*1000;
bool is_prime[LIMIT];

int slide(int n,int base){
      return (n%10)*(base/10)+n/10;
}

int main(){
      memset(is_prime,true,sizeof(is_prime));
      is_prime[0]=is_prime[1]=false;
      int s,add;
      for(int i=2;i*i<LIMIT;i++){
            if(is_prime[i]==false)continue;
            if(i==2){
                  s=4;
                  add=2;
            }else{
                  s=i*i;
                  add=2*i;
            }
            for(int j=s;j<LIMIT;j+=add){
                  is_prime[j]=false;
            }
      }
      int base=10;
      int roopSize=0;
      int ans=0;
      for(int i=2;i<LIMIT;i++){
            if(is_prime[i]==false)continue;
            if(i>base){
                  base*=10;
                  roopSize++;
            }
            bool isRoopNum=true;
            int t=i;
            for(int i=0;i<roopSize;i++){
                  t=slide(t,base);
                  if(is_prime[t]==false)isRoopNum=false;
            }
            ans+=isRoopNum;
      }
      printf("%d\n",ans);
}