连续100个整数末尾加上11后都是合数

gxqcn

to mathe: 你的算法应该是筛法吧，MAX_PRIME 为 655360，可筛选的范围应在32bit内， 按说能得到的最大结果应不超出 2^32-1 去掉最后两位（十进制下）， 所以我对你 f[125]=167369311 起的数据表示不确信，尽管它可能是正确的。

——对不起，看错了。参见 25#

无心人

昨天下午就解完了，利用空余时间 结果没时间发，学校网没接到新楼 晚上也忘了发

无心人

/* (x * 100 + 11) == 0 mod p x * 100 == p - 11 mod p p = 3 x * 100 == 3 - 2 mod 3 x == 1 mod 3 p = 7 x * 100 == 7 - 4 mod 7 x * 2 == 3 mod 7 x == 5 mod 7 p = 11 x * 100 == 0 mod 11 x == 0 mod 11 p > 11 x * 100 + 11 == 0 mod p x * 100 == (p - 11) mod p x == (p - 11) * 100^(-1) mod p */ #include #include #define MAX 100000000 #define SieveNumber 65536 int Prime[9999]; int Cache[SieveNumber]; int P; int P11[MAX]; int g = 0; /* ExtendedEuclid(e,f) 1 （X1,X2,X3):=(1,0,f) 2 (Y1,Y2,Y3):=(0,1,e) 3 if (Y3=0) then return e'=null//无逆元 4 if (Y3=1) then return e'=Y2 //Y2为逆元 5 Q:=X3 div Y3 6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3) 7 （X1,X2,X3):=(Y1,Y2,Y3) 8 (Y1,Y2,Y3):=(T1,T2,T3) 9 goto 3 */ int inv100(int p) { int e = 100, f = p; int X1 = 1, X2 = 0, X3 = f; int Y1 = 0, Y2 = 1, Y3 = e; int Q, T1, T2, T3; while (1) { Q = X3 / Y3; T1 = X1 - Q * Y1; T2 = X2 - Q * Y2; T3 = X3 - Q * Y3; X1 = Y1; X2 = Y2; X3 = Y3; Y1 = T1, Y2 = T2, Y3 = T3; if (Y3 == 0) return (0); if (Y3 == 1) return (Y2 % p); } } void init() { int i; Prime[0] = 2; Prime[1] = 3; Prime[2] = 5; Prime[3] = 7; Prime[4] = 11; Prime[5] = 13; for (i = 0; i < MAX; i ++) P11[i] = 1; } void sieve() { int i, j, p; for (i = 0; i <= 10; i ++) Cache[i] = 0; for (i = 12; i <= SieveNumber-1; i += 2) Cache[i] = 0; for (i= 11; i <= SieveNumber-1; i += 2) Cache[i] = 1; for (j = 1; j <= 5; j ++) for (i = Prime[j] * Prime[j]; i <= SieveNumber-1; i += 2 * Prime[j]) Cache[i] = 0; p = 6; for (i = 16; i <= 256; i ++) if (Cache[i] == 1) Prime[p++] = i; for (j = 6; j < p ; j ++) for (i = Prime[j] * Prime[j]; i <= SieveNumber-1; i += 2 * Prime[j]) Cache[i] = 0; for (i = 256; i <= SieveNumber-1; i ++) if (Cache[i] == 1) Prime[p ++] = i; P = p; } void initP11() { int i, j, k; for (i = 1; i < MAX; i += 3) P11[i] = 0; for (i = 5; i < MAX; i += 7) P11[i] = 0; for (i = 11; i < MAX; i += 11) P11[i] = 0; for (j = 5; j < P; j ++) { k = (Prime[j] - 11) * inv100(Prime[j]) % Prime[j]; for (i = k; i < MAX; i += Prime[j]) P11[i] = 0; } for (i = 1; i < P; i ++) if ((Prime[i] >= 11) && ((Prime[i] - 11) % 100 == 0)) P11[(Prime[i]-11)/100] = 1; } void checkP11() { int i; int prev = 0; for (i = 0; i < MAX; i ++) if (P11[i] == 1) { if ((i - prev) > g) { g = i - prev; printf("Find: %d, start %d!\n", g - 1, (prev + 1)); } prev = i; } } int main() { init(); sieve(); initP11(); checkP11(); return (0); } /* Find: 1, start 1! Find: 4, start 4! Find: 5, start 10! Find: 7, start 43! Find: 10, start 145! Find: 14, start 361! Find: 16, start 448! Find: 20, start 652! Find: 21, start 4347! Find: 22, start 5605! Find: 26, start 6217! Find: 31, start 8083! Find: 34, start 8452! Find: 41, start 23284! Find: 43, start 44875! Find: 44, start 46711! Find: 49, start 80101! Find: 51, start 175623! Find: 54, start 220659! Find: 65, start 357075! Find: 70, start 1239046! Find: 78, start 4225245! Find: 98, start 4242612! Find: 99, start 7135851! Find: 124, start 23717773! */

wayne

是这个结果。 我算到50时，已经过了2分钟，不想再等了。 发现结果跟mathe一样。 后来，直接检验23717773，是正确的

gxqcn

21# gxqcn 刚才才注意到，MAX_PRIME 为 655360（后面比 2^16 多个零）， 所以我在 21# 的担心是多余的。

无心人

哈 我还纳闷呢，你说的我看不明白，似乎矛盾呢 原来你看错了啊

mathabc

素数（或合数）的确魅力无穷啊，随便一演化就是一个问题...

KeyTo9_Fans

循环利用buf数组可以实现更大的规模的检测，具体方法如下： 将buf数组设为int类型，记录当前的数是被哪个素数筛掉的。如果没有被筛掉，则记为0。 初始化buf数组： 对于素数p（2和5除外），找最小的i，使得(i*100+11)%p=0，且i*100+11>p。 如果buf[i]未标记，则把buf[i]标记为p，否则看buf[i+p]是否做了标记， 如果buf[i+p]未标记，则把buf[i+p]记为p，否则看buf[i+p+p]是否做了标记……依次类推。 素数p的范围是根据你想要搜查的范围决定的。 若要搜查11到(n*100+11)，则使用p<=sqrt(n*100+11)的素数标记buf数组。 当然，也可以在检测阶段根据当前检测到的n，同步地把sqrt(n*100+11)的素数加入buf数组。 循环扫描buf数组： 从buf[0]开始逐个检测。 如果buf[i]的标记为0，则遇到了一个尾数为11的素数。 如果buf[i]的标记非0，则把buf[i]的标记往后“踢”。 设buf[i]的标记为k，则把此标记“踢”到buf[i+k]里。 但如果buf[i+k]已经有非0标记了，则把标记k踢到buf[i+k+k]里……依次类推。 buf数组是循环利用的。 一旦发现i+k+k+……超出范围，则回到buf[0]，继续往后数超出的部分。 该算法的时间复杂度： 与传统筛法的时间复杂度完全相同，为O(n*ln(ln(n)))。 加速方案： 把最小的几个素数频繁地踢来踢去是很浪费时间的。 所以把素数3、7、11、13、17、19、23拿出来单独考虑， 组成一段长达3*7*11*13*17*19*23=22309287的周期T。 即这些素数每经过22309287次检测就会回到初始状态。 所以把buf的长度设为T，并把这些素数在T步内的状态预处理出来，记在另一个长度为T的辅助数组里。 在辅助数组的帮助下，buf里的素数可以直接从29开始标起。 于是把buf里的标记往后踢的操作明显减少，扫描速度增至原来的2倍。 不足之处： 由于踢标记的操作步骤本来就比传统筛法多（多次赋值和越界回归）， 所以即使采取了加速措施，扫描速度仍比不上mathe的传统筛法。 他的扫描速度为23.7M/s，而我的扫描速度只有13.4M/s。（"M"表示100万个尾数为11的数） 计算结果： Marking first T p11 with 3,7,11,13,17,19,23... Creating prime table... Creating buf mark... max_c=7171, T=22309287 Checking from 0 to max_c*T... 0T 4: 4 10: 5 43: 7 145: 10 361: 14 448: 16 652: 20 4347: 21 5605: 22 6217: 26 8083: 31 8452: 34 23284: 41 44875: 43 46711: 44 80101: 49 175623: 51 220659: 54 357075: 65 1239046: 70 4225245: 78 4242612: 98 7135851: 99 23717773: 124 167369311: 143 339898777: 157 1307096556: 165 1550482953: 170 100T 3539248312: 209 200T 300T 400T 500T 600T 700T 800T 900T 1000T 1100T 25931959342: 212 1200T 1300T 1400T 1500T 1600T 1700T 1800T 1900T 42420271605: 215 2000T 45200835568: 217 2100T 2200T 2300T 2400T 2500T 2600T 2700T 2800T 2900T 3000T 3100T 3200T 3300T 3400T 3500T 3600T 3700T 3800T 3900T 4000T 4100T 4200T 4300T 4400T 4500T 4600T 4700T 4800T 4900T 5000T 5100T 5200T 5300T 5400T 5500T 5600T 5700T 5800T 5900T 6000T 135910429320: 239 6100T 6200T 6300T 6400T 6500T 6600T 6700T 6800T 6900T 7000T 7100T 用时：3h15min 速度：0.6T/s

KeyTo9_Fans

上述算法可以从任意一个周期开始。 因为可以根据要开始的周期数来初始化buf数组。 所以只要计算相应的质数经过若干周期之后被踢到的起始位置即可。 昨晚从7100T开始继续通宵运行程序，结果如下： Marking first T p11 with 3,7,11,13,17,19,23... Creating prime table... Creating buf mark at 7100T... max_c=22412, T=22309287 Checking from 7100T to max_c*T... 7200T 7400T 7600T 7800T 178250544328: 259 8000T 8200T 8400T 8600T 8800T 9000T 9200T 9400T 9600T 9800T 10000T 10200T 10400T 10600T 10800T 11000T 11200T 11400T 11600T 11800T 12000T 12200T 12400T 12600T 12800T 13000T 13200T 13400T 13600T 13800T 14000T 14200T 14400T 14600T 14800T 15000T 15200T 15400T 15600T 15800T 16000T 16200T 16400T 16600T 16800T 17000T 17200T 17400T 17600T 17800T 18000T 18200T 18400T 18600T 18800T 19000T 19200T 430527575403: 270 19400T 19600T 19800T 20000T 20200T 20400T 20600T 20800T 21000T 21200T 21400T 21600T 21800T 22000T 22200T 22400T 速度：0.51T/s 用时：8h20min 有空的话以后还可以继续跑。 另外，0到(n*100+11)之内尾数为11的连续合数个数的最大值可以用以下式子估计： max_combo = 1/r * ln(n) 其中r是0到(n*100+11)之内尾数为11的质数所占的比例，可用如下式子估算： r = 2/3 * 6/7 * 10/11 * 12/13 * 16/17 * 18/19 * 22/23 * ... * (p-1)/p 其中p取到sqrt(n)为止。 按理说应该是sqrt(n*100+11)，但实际上取sqrt(n)更接近测试结果。 当n→∞时，r≈c/ln(n)，所以 max_combo ≈ c(ln(n))^2 其中，c是某常数 经最小二乘法拟合max_combo和ln(n)，得 c=0.368 (是1/e吗?)，标准差为5，相关系数为0.998 其中，仅测试跳变点，且取跳变之前的值 例如: max_combo在430527575403处从259跳变为270，则认为f(ln(430527575403))=259

mathe

我觉得如同搜索素数的算法一样，采用分段筛选的方法就可以了。这样还是可以采用比特位的方法来保存数据。