http://poj.org/problem?id=2635

因為給定的k是兩個素數的乘機，所以該數所包含的因子是{1,K,p,q}假設k = p*q p,q為素數,所以只要從小到大枚舉小于L的素數，只要能夠整出，就說明p已經求得，否則則不存在。這里關鍵是k< 10^100次方，普通數據類型無法直接輸入，所以要模你除法，這里將k轉換成1000進制的數然后模擬除法。如果是10進制的數模擬除法是時間復雜度會是O(10^8)會超時。

View Code #include <stdio.h> #include <string.h> #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; }

?

總結

以上是生活随笔為你收集整理的pku 2635 The Embarrassed Cryptographer 数论——素数筛选法+模拟大数除法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。