poj-2635-The Embarrassed Cryptographer

進制轉化+篩選法求素數。 題意： 給你兩個數m,n；m是兩個素數的乘。如果這兩個素數中最小的那個小於（是小於！！！！）n的話，就輸出BAD 那個數；否則輸出GOOD； 做法： 先用素數篩把小於1100000的素數都找出來。 然後把m轉化為千進制。 對於一個m，把i從2到n遍歷一遍，如果i為素數&&m%i==0，說明m可以整除i； [html]   #include<iostream>   #include<stdio.h>   #include<math.h>   #include<string.h>   using namespace std;   #define Max 1100000   int isp[Max];   void isprim()   {       int i,j;       isp[0]=isp[1]=0;       isp[2]=1;       for(i=3;i<Max;i++)           isp[i]=i%2;       int ns;       ns=(int)sqrt(Max*1.0);       for(i=3;i<=ns;i++)       {           if(isp[i])           {               for(j=i*2;j<Max;j+=i)                   isp[j]=0;           }       }   }   int main()   {       int len,n,i,j,k,ks;       int num,nums;       char str[1000];       isprim();       while(scanf("%s%d%*c",str,&n)&&(!(str[0]=='0'&&n==0)))       {           len=strlen(str);           for(k=2;k<n;k++)           {               if(isp[k]==0)               {                   continue;               }               num=0;               for(i=0;i<len;i+=3)               {                   nums=0;                   ks=1;                   for(j=i;j<i+3&&j<len;j++)                   {                       ks=ks*10;                       nums=nums*10+(str[j]-'0');                   }                   num=num*ks+nums;                   num=num%k;               }            //   printf("num=%d,k=%d\n",num,k);               if(num==0)               {                   printf("BAD %d\n",k);                   break;               }           }           if(k==n)printf("GOOD\n");       }       return 0;   }