学到三点:
1:素数的打表模板
int yes[SIZE]; void find_prim() { int temp=sqrt(SIZE)+0.5; memset(yes,0,sizeof(yes)); for(int i=2;i<=temp;i++) if(!yes[i]) { for(int j=i*i;j<SIZE;j+=i) yes[j]=1; } }
2:千进制
Char格式读入K,把K转成千进制,同时变为int型.
把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间,会TLE。
例如,把K=1234567890转成千进制,就变成了:Ktemp=[ 1][234][567][890]。
3:高精度求模-同余模定理
例如要验证123是否被3整除,只需求模124%3
但当123是一个大数时,就不能直接求,只能通过同余模定理对大数“分块”间接求模
具体做法是:
先求1%3 = 1
再求(1*10+2)%3 = 0
再求 (0*10+4)% 3 = 1
那么就间接得到124%3=1,这是显然正确的
而且不难发现, (1*10+2)*10+4 = 124
这是在10进制下的做法,千进制也同理,*10改为*1000就可以了
#include <iostream> #include <cmath> #include <cstring> using namespace std; const int SIZE = 1000005; int yes[SIZE]; char str[120]; int L, K[100]; int m; void find_prim() { int temp=sqrt(SIZE)+0.5; memset(yes,0,sizeof(yes)); for(int i=2;i<=temp;i++) if(!yes[i]) { for(int j=i*i;j<SIZE;j+=i) yes[j]=1; } } void trans() { int len=strlen(str); m=0; for(int i=len-1;i>=0;i-=3) { K[m]=0; for(int j=max(i-2,0);j<=i;j++) K[m]=K[m]*10+(str[j]-'0'); m++; } } int module(int j) { int r=0; for(int i=m-1;i>=0;i--) r=(r*1000+K[i])%j; return r; } int main() { int i; find_prim(); while(1) { cin>>str>>L; if(!strcmp(str,"0") && !L) break; trans(); for(i=2;i<L;i++) if(!yes[i] && !module(i)) { cout<<"BAD "<<i<<endl; break; } if(i>=L) cout<<"GOOD\n"; } return 0; }