学步园

自己写的，留着以后做求质数表的和高精度除法的模板。

#include "math.h"<br /> #include <iostream><br /> using namespace std;<br /> int K[35],K_index,L;<br /> bool isprime[1000005];<br /> void prime(bool a[],int max_n)//生成质数表<br /> {<br /> memset(a,1,sizeof(bool)*max_n);//初始化参数数组，要特别小心 我一开始直接用memset(a,1,sizeof(a))，是错的<br /> a[0]=a[1]=false;<br /> int sq=sqrt((double)max_n);<br /> for(int i=2;i<=sq;i++)<br /> {<br /> if(a[i])<br /> {<br /> for(int j=i*i;j<=max_n;j+=i)<br /> {<br /> a[j]=false;<br /> }</p> <p> }<br /> }<br /> }<br /> int divid(int t,int* big_num,int end)//高精度除法，返回余数 这里是1000进制<br /> {<br /> int left=0;<br /> for(int i=0;i<end;i++)<br /> {<br /> left=left*1000+big_num[i];<br /> left=left%t;<br /> }<br /> return left;<br /> }<br /> int translate(char *str,int* int_array)//输入字符串，转换成int[]存储的大数，这里用的1000进制，返回int[]末端的index<br /> {<br /> int len=strlen(str);<br /> int k,temp,K_index;<br /> k=len%3;<br /> K_index=temp=0;<br /> for(int i=0;i<k;i++)<br /> {<br /> temp=temp*10;<br /> temp+=str[i]-'0';<br /> }<br /> if(temp) int_array[K_index++]=temp;<br /> for(int i=k;i<len;i=i+3)<br /> {<br /> temp=0;<br /> for(int j=0;j<3;j++)<br /> {<br /> temp=temp*10;<br /> temp+=str[i+j]-'0';<br /> }<br /> int_array[K_index++]=temp;<br /> }<br /> return K_index;<br /> }<br /> int main()<br /> {<br /> prime(isprime,1000005);<br /> char temp[105];<br /> while(scanf("%s%d",temp,&L)&&L)<br /> {<br /> int K_end=translate(temp,K);<br /> int dd;<br /> for(dd=2;dd<L;dd++)<br /> {<br /> if(isprime[dd]&&!divid(dd,K,K_end)) break;<br /> }<br /> if(dd>=L) printf("GOOD/n");<br /> else printf("BAD %d/n",dd);<br /> }<br /> return 0;<br /> }<br />