因为给定的k是两个素数的乘机，所以该数所包含的因子是{1,K,p,q}假设k = p*q p,q为素数,所以只要从小到大枚举小于L的素数，只要能够整出，就说明p已经求得，否则则不存在。这里关键是k< 10^100次方，普通数据类型无法直接输入，所以要模你除法，这里将k转换成1000进制的数然后模拟除法。如果是10进制的数模拟除法是时间复杂度会是O(10^8)会超时。
View Code #include#include #define maxn 1000007int f[maxn],p[maxn];int ans[40];char K[107];int L,len,anslen;//素数筛选法打表void Prim(){ int i,j; len = 0; memset(f,0,sizeof(f)); f[0] = f[1] = 1; for (i = 2; i*i < maxn; ++i) { if (!f[i]) { for (j = 2*i; j < maxn; j = j + i) { f[j] = 1; } } } for (i = 2; i < maxn; ++i) { if (!f[i]) p[len++] = i; } /*for (i = 0; i <= 50; ++i) { printf("%d ",p[i]); } printf("\n");*/}//将K转化曾1000进制数void convert(){ int i; int lenx = strlen(K); memset(ans,0,sizeof(ans)); anslen = 0; i = 0; if (lenx%3 != 0) { for (; i < lenx%3; ++i) { ans[0] = ans[0]*10 + K[i] - '0'; } anslen++; } //printf(">>>>>>>>>>>%d\n",anslen); while (i < lenx) { ans[anslen] = (K[i] - '0')*100 + (K[i + 1] - '0')*10 + (K[i + 2] - '0'); i += 3; anslen++; //puts("TEST"); } }//模拟除法int mod(int x){ int i; int tmp = 0; for (i = 0; i < anslen; ++i) { tmp = (ans[i] + tmp*1000)%x; } return tmp;}int main(){ int i; Prim(); while (scanf("%s%d",K,&L)) { if (!strcmp(K,"0") && !L) break; convert(); //循环查找 for (i = 0; p[i] < L; ++i) { if (!mod(p[i])) break; } if (p[i] >= L) printf("GOOD\n"); else printf("BAD %d\n",p[i]);; } return 0;}