版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/chaoweilanmao/article/details/33417423
这道题一看是大数题就知道不会做。就看了一下其它人的解题报告，千篇一律的做法：
首先把大数变成千进制数用整形数组存起来，事实上所谓千进制就是每三位数当作一位数处理。
附上千进制和万进制的两种做法的代码，事实上几乎相同，例如以下：
另外从这里http://blog.csdn.net/lyy289065406/article/details/6648530学到了一个推断素数的比較快的方法，就是首先推断这个数是不是偶数，假设不是再枚举小于或等于这个数的平方根的素数，看是不是能够使这个数被整除。假设再不是，那么这个数肯定是素数了。
首先把大数变成千进制数用整形数组存起来，事实上所谓千进制就是每三位数当作一位数处理。
然后从小到大枚举全部小于L的素数。用同余模的各种知识对这个转换后的千进制数进行求余，这个所谓同余模处理，事实上就是。设两个正整数a,b,c,有(a+b)%c=(a%c+b)%c，至于证明的话，
我不会。
最后呢，假设余数为0那么输出BAD 比L小的K质因子。假设不是的话，输出GOOD。
嗯，这样做就好了。至于为毛是千进制。事实上百进制，十进制都能够，用整形数组存起来表示即可了，不过千进制在这里是进行求余过程最优的方法，由于能使求余次数最少。那么为毛不能用万进制，由于会超精的。为毛？由于你想L最大是10的6次方，比它小的素数最大是有6位数的，于是每次对数组里面的每一个元素取完一次余，得到的最大余数最大也是有6位数的，于是之后
假设是万进制就要乘以10的4次方加上后面的数组元素，于是最多就会有10位数，int能表示的最大数是2的十次方的样子多一点，当然这里假设用long long的话是能够用万进制的，由于他们都是用千进制。所以。我不只用千进制的方法写了。还用万进制的方法写了。
附上千进制和万进制的两种做法的代码，事实上几乎相同，例如以下：
#include<iostream>
#include<cstring>
using namespace std;
int prime[1000000],sushu,l,num[110],shumu;
char k[110];
bool isprime(int x)
{
int i;
if(x%2==0)
return 0;
for(i=0;prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0)
return 0;
return 1;
}
void makeprime()
{
int i;
prime[0]=2;
for(sushu=1,i=3;;i++)
if(isprime(i))
{
prime[sushu++]=i;
if(i>=1000000)
break;
}
}
void makenum()
{
bool flag=1;
int s,e,i,n=strlen(k),j,sum;
shumu=0;
for(e=n-1;flag;e=s-1)
{
if(e-2<=0)
{
s=0;
flag=0;
}
else
s=e-2;
sum=0;
for(j=s;j<=e;j++)
sum=sum*10+(k[j]-'0');
num[shumu++]=sum;
}
}
void iscunzai()
{
makenum();
int i,j,r;
for(i=0;prime[i]<l;i++)
{
r=0;
for(j=shumu-1;j>-1;j--)
r=(r*1000+num[j])%prime[i];
if(r==0)
{
printf("BAD %d
",prime[i]);
return;
}
}
printf("GOOD
");
}
int main()
{
makeprime();
while(scanf("%s%d",k,&l)&&(k[0]!='0'||l!=0))
{
iscunzai();
}
}#include<iostream>
#include<cstring>
using namespace std;
int prime[1000000],sushu,l,num[110],shumu;
char k[110];
bool isprime(int x)
{
int i;
if(x%2==0)
return 0;
for(i=0;prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0)
return 0;
return 1;
}
void makeprime()
{
int i;
prime[0]=2;
for(sushu=1,i=3;;i++)
if(isprime(i))
{
prime[sushu++]=i;
if(i>=1000000)
break;
}
}
void makenum()
{
bool flag=1;
int s,e,i,n=strlen(k),j,sum;
shumu=0;
for(e=n-1;flag;e=s-1)
{
if(e-3<=0)
{
s=0;
flag=0;
}
else
s=e-3;
sum=0;
for(j=s;j<=e;j++)
sum=sum*10+(k[j]-'0');
num[shumu++]=sum;
}
}
void iscunzai()
{
makenum();
int i,j;
long long r;
for(i=0;prime[i]<l;i++)
{
r=0;
for(j=shumu-1;j>-1;j--)
r=(r*10000+num[j])%prime[i];
if(r==0)
{
printf("BAD %d
",prime[i]);
return;
}
}
printf("GOOD
");
}
int main()
{
makeprime();
while(scanf("%s%d",k,&l)&&(k[0]!='0'||l!=0))
{
iscunzai();
}
}另外从这里http://blog.csdn.net/lyy289065406/article/details/6648530学到了一个推断素数的比較快的方法，就是首先推断这个数是不是偶数，假设不是再枚举小于或等于这个数的平方根的素数，看是不是能够使这个数被整除。假设再不是，那么这个数肯定是素数了。