to mathe:
你的算法应该是筛法吧，MAX_PRIME 为 655360，可筛选的范围应在32bit内，
按说能得到的最大结果应不超出 2^32-1 去掉最后两位（十进制下），
所以我对你 f=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 <stdio.h>
#include <stdlib.h>
#define MAX 100000000
#define SieveNumber 65536
int Prime;
int Cache;
int P;
int P11;
int g = 0;
/*
ExtendedEuclid(e,f)
1 （X1,X2,X3):=(1,0,f)
2(Y1,Y2,Y3):=(0,1,e)
3if (Y3=0) then returne'=null//无逆元
4if (Y3=1) then returne'=Y2//Y2为逆元
5Q:=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)
9goto 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 = 2;
Prime = 3;
Prime = 5;
Prime = 7;
Prime = 11;
Prime = 13;
for (i = 0; i < MAX; i ++)
P11 = 1;
}
void sieve()
{
int i, j, p;
for (i = 0; i <= 10; i ++)
Cache = 0;
for (i = 12; i <= SieveNumber-1; i += 2)
Cache = 0;
for (i= 11; i <= SieveNumber-1; i += 2)
Cache = 1;
for (j = 1; j <= 5; j ++)
for (i = Prime * Prime; i <= SieveNumber-1; i += 2 * Prime)
Cache = 0;
p = 6;
for (i = 16; i <= 256; i ++)
if (Cache == 1)
Prime = i;
for (j = 6; j < p ; j ++)
for (i = Prime * Prime; i <= SieveNumber-1; i += 2 * Prime)
Cache = 0;
for (i = 256; i <= SieveNumber-1; i ++)
if (Cache == 1)
Prime = i;
P = p;
}
void initP11()
{
int i, j, k;
for (i = 1; i < MAX; i += 3)
P11 = 0;
for (i = 5; i < MAX; i += 7)
P11 = 0;
for (i = 11; i < MAX; i += 11)
P11 = 0;
for (j = 5; j < P; j ++)
{
k = (Prime - 11) * inv100(Prime) % Prime;
for (i = k; i < MAX; i += Prime)
P11 = 0;
}
for (i = 1; i < P; i ++)
if ((Prime >= 11) && ((Prime - 11) % 100 == 0))
P11[(Prime-11)/100] = 1;
}
void checkP11()
{
int i;
int prev = 0;
for (i = 0; i < MAX; i ++)
if (P11 == 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!
*/
是这个结果。
我算到50时，已经过了2分钟，不想再等了。
发现结果跟mathe一样。
后来，直接检验23717773，是正确的
21# gxqcn
刚才才注意到，MAX_PRIME 为 655360（后面比 2^16 多个零），
所以我在 21# 的担心是多余的。:loveliness:
哈
我还纳闷呢，你说的我看不明白，似乎矛盾呢
原来你看错了啊
素数（或合数）的确魅力无穷啊，随便一演化就是一个问题...
循环利用buf数组可以实现更大的规模的检测，具体方法如下：
将buf数组设为int类型，记录当前的数是被哪个素数筛掉的。如果没有被筛掉，则记为0。
初始化buf数组：
对于素数p（2和5除外），找最小的i，使得(i*100+11)%p=0，且i*100+11>p。
如果buf未标记，则把buf标记为p，否则看buf是否做了标记，
如果buf未标记，则把buf记为p，否则看buf是否做了标记……依次类推。
素数p的范围是根据你想要搜查的范围决定的。
若要搜查11到(n*100+11)，则使用p<=sqrt(n*100+11)的素数标记buf数组。
当然，也可以在检测阶段根据当前检测到的n，同步地把sqrt(n*100+11)的素数加入buf数组。
循环扫描buf数组：
从buf开始逐个检测。
如果buf的标记为0，则遇到了一个尾数为11的素数。
如果buf的标记非0，则把buf的标记往后“踢”。
设buf的标记为k，则把此标记“踢”到buf里。
但如果buf已经有非0标记了，则把标记k踢到buf里……依次类推。
buf数组是循环利用的。
一旦发现i+k+k+……超出范围，则回到buf，继续往后数超出的部分。
该算法的时间复杂度：
与传统筛法的时间复杂度完全相同，为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
上述算法可以从任意一个周期开始。
因为可以根据要开始的周期数来初始化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
我觉得如同搜索素数的算法一样，采用分段筛选的方法就可以了。这样还是可以采用比特位的方法来保存数据。