usaco_pprime.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:pprime
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
using namespace std;
int i=0,num,a,b;
int checked[10000];
int qq[8]={10000000,1000000,100000,10000,1000,100,10,1};
int nums[5];
bool isprime(int a)
{
   if(a==0) return false;
   for(int i=2;i<=int(sqrt(a));i++)
     if(a%i==0) return false;
   return true;
}
void searchdigi(int t)
{
     int j;
     if(t>1) 
       for(j=0;j<10;j++) {nums[t]=j;searchdigi(t-1);}
     else 
     {
          if(nums[0]==1) 
          {for(j=0;j<10;j++) 
              {num=j;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
          else if(nums[0]==2) 
          {for(j=0;j<10;j++) 
              {num=j*10+j;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
          else if(nums[0]==3) 
          {for(j=0;j<10;j++) 
              {num=j+nums[2]*10+j*100;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
          else if(nums[0]==4) 
          {for(j=0;j<10;j++) 
              {num=j+nums[2]*10+nums[2]*100+j*1000;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
          else if(nums[0]==5) 
          {for(j=0;j<10;j++) 
              {num=j+nums[2]*10+nums[3]*100+nums[2]*1000+j*10000;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
          else if(nums[0]==6) 
          {for(j=0;j<10;j++) 
              {num=j+nums[2]*10+nums[3]*100+nums[3]*1000+nums[2]*10000+j*100000;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
          else
          {for(j=0;j<10;j++) 
              {num=j+nums[2]*10+nums[3]*100+nums[4]*1000+nums[3]*10000+nums[2]*100000+j*1000000;
               if(num<=b && num>=a && isprime(num)) {checked[i]=num;i++;}
              }
          }
     }
}
int main()
{
    ifstream fin ("pprime.in");
    ofstream fout ("pprime.out");
    fin>>a>>b;
    int digi,q=1;    
    for(i=0;i<10000;i++) checked[i]=10000000;
    i=0;
    for(digi=1;digi<8;digi++)
    {
        nums[0]=digi;
        searchdigi((digi+1)/2);
    }
    sort(checked,checked+i);
    i=0;
    while(checked[i]<10000000)
    {
        fout<<checked[i]<<endl;
        i++;
    }
    //system("PAUSE");
    return 0;
}