プロジェクトオイラー Problem 51 「素数の桁置換」 †

Problem 51 「素数の桁置換」 †

*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.

56**3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

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

上限を定めて地道に全探索しても結構何とかなるものです。
値を増加させて全部の変化を試しています。
昔この問題に挑戦した時はもっと賢い解法を書いてたような気がします。


#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
#include<time.h>


const int LIMIT=1000000;
bool is_prime[LIMIT+1];

bool changeIsPrime(int n,int changeN,int bit){
      int result=0;
      int base=1;
      int memoN=-1;
      bool ok=true;
      while(n>0){
            int t=n%10;
            if((n<10)&&(changeN==0)&&(bit%2==1)){
                  ok=false;
            }
            if((bit%2==1)&&((memoN==-1)||(memoN==t))){
                  result+=changeN*base;
                  memoN=t;
            }else if((bit%2==1)&&(memoN!=t)){
                  ok=false;
            }else{
                  result+=t*base;
            }
            bit/=2;
            n/=10;
            base*=10;
      }
      return ok&&is_prime[result];
}

int main(){
      clock_t start,end;
      start = clock();
   
      memset(is_prime,true,sizeof(is_prime));
      is_prime[0]=is_prime[1]=false;
      for(int i=2;i*i<=LIMIT;i++){
            if(is_prime[i]==false)continue;
            int start=4;
            int add=2;
            if(i%2==1){
                  start=i*i;
                  add=i*2;
            }
            for(int j=start;j<=LIMIT;j+=add){
                  is_prime[j]=false;
            }
      }
      int bits[]={2,4,8,16,32,64};
      int ans=0;
      for(int i=2;i<LIMIT;i++){
            if(is_prime[i]==false)continue;
            int bitMax=bits[(int)log10(i)];
            bool hit=false;
            for(int bit=1;bit<bitMax;bit++){
                  int count=0;
                  for(int j=0;j<=9;j++){
                        count+=changeIsPrime(i,j,bit);
                  }
                  if(count==8){
                        ans=i;
                        hit=true;
                        break;
                  }
            }
            if(hit)break;
      }
      end = clock();
      printf("%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
      printf("%d\n",ans);
}