数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 连续100个整数末尾加上11后都是合数
1234下一页
返回列表 发新帖
楼主: 056254628

[擂台] 连续100个整数末尾加上11后都是合数

[复制链接]
mathe
发表于 2009-10-8 15:33:06 | 显示全部楼层
贴一段使用了HugeCalc的代码(其实就是为了求素数和数论倒数的代码)

  2. #define BUF_LEN (1<<27)
  3. #define MAX_PRIME 655360
  4. int mask[BUF_LEN];
  5. unsigned plist[MAX_PRIME];
  6. int pc;
  7. #define GETWORD(x)  ((x)>>5)
  8. #define GETOFF(x)   ((x)&31)
  9. #define OFFBIT(x)   (1<<GETOFF(x))
  10. #define SET_BIT(x)  (mask[GETWORD(x)]|=OFFBIT(x))
  11. #define TEST_BIT(x) ((mask[GETWORD(x)]&OFFBIT(x))!=0)
  12. void unmask(int prime)
  13. {
  14.         int inv=HugeCalc::InvertMod(100,prime);
  15.         int u=prime-11;
  16.         while(u<0)u+=prime;
  17.         u*=inv;
  18.         u%=prime;
  19.         if(u*100+11!=prime){
  20.                 SET_BIT(u);
  21.         }
  22.         unsigned v=u+prime;
  23.         for(;v>prime;v+=prime){
  24.                 SET_BIT(v);
  25.         }
  26. }

  28. void check_list()
  29. {
  30.         int cur_len=0;
  31.         int max_len=0;
  32.         unsigned v=0;
  33.         do{
  34.                 if(TEST_BIT(v)){
  35.                         cur_len++;
  36.                         if(cur_len>max_len){
  37.                                 printf("f[%d]=%u\n",cur_len,v-cur_len+1);
  38.                                 max_len=cur_len;
  39.                         }
  40.                 }else{
  41.                         cur_len=0;
  42.                 }
  43.         }while(++v!=0);
  44. }

  46. int main()
  47. {
  48.         HugeCalc::EnableTimer();
  49.         pc=HugeCalc::GetPrimeList(plist,MAX_PRIME,7,MAX_PRIME);
  50.         unmask(3);
  51.         unsigned timer=HugeCalc::GetTimer();
  52.         int i;
  53.         printf("Total num prime %d, %dus\n",pc,timer);
  54.         for(i=0;i<pc;i++){
  55.                 unmask(plist[i]);
  56.                 if(i%100==99){
  57.                         timer=HugeCalc::GetTimer();
  58.                 }
  59.         }
  60.         timer=HugeCalc::GetTimer();
  61.         printf("Total prime masked,%dus\n",timer);
  62.         check_list();
  63.         timer=HugeCalc::GetTimer();
  64.         printf("Total cost %dus\n",timer);
  65. }
复制代码
可以计算到f(131)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-8 15:36:23 | 显示全部楼层
f[1]=1
f[2]=4
f[3]=4
f[4]=4
f[5]=4
f[6]=43
f[7]=43
f[8]=145
f[9]=145
f[10]=145
f[11]=145
f[12]=145
f[13]=145
f[14]=145
f[15]=145
f[16]=145
f[17]=652
f[18]=652
f[19]=652
f[20]=652
f[21]=4347
f[22]=4902
f[23]=4902
f[24]=5248
f[25]=5248
f[26]=5248
f[27]=8083
f[28]=8083
f[29]=8083
f[30]=8083
f[31]=8083
f[32]=8083
f[33]=8083
f[34]=8083
f[35]=8083
f[36]=8083
f[37]=8083
f[38]=38335
f[39]=44875
f[40]=44875
f[41]=44875
f[42]=44875
f[43]=44875
f[44]=46711
f[45]=51481
f[46]=51481
f[47]=80101
f[48]=80101
f[49]=80101
f[50]=223312
f[51]=223312
f[52]=223312
f[53]=223312
f[54]=417643
f[55]=417643
f[56]=417643
f[57]=417643
f[58]=417643
f[59]=417643
f[60]=417643
f[61]=417643
f[62]=417643
f[63]=417643
f[64]=417643
f[65]=1239046
f[66]=1239046
f[67]=1239046
f[68]=1239046
f[69]=1239046
f[70]=1239046
f[71]=1767661
f[72]=3848451
f[73]=4157752
f[74]=4157752
f[75]=4543498
f[76]=4543498
f[77]=4543498
f[78]=4543498
f[79]=4543498
f[80]=4543498
f[81]=4543498
f[82]=4543498
f[83]=4543498
f[84]=4543498
f[85]=4543498
f[86]=5346948
f[87]=5346948
f[88]=5346948
f[89]=5346948
f[90]=5346948
f[91]=5346948
f[92]=5346948
f[93]=5346948
f[94]=5346948
f[95]=5346948
f[96]=5346948
f[97]=5346948
f[98]=5346948
f[99]=5346948
f[100]=5346948
f[101]=5346948
f[102]=5346948
f[103]=5346948
f[104]=5346948
f[105]=5346948
f[106]=5346948
f[107]=5346948
f[108]=5346948
f[109]=5346948
f[110]=5346948
f[111]=5346948
f[112]=78072010
f[113]=78072010
f[114]=78072010
f[115]=78072010
f[116]=78072010
f[117]=78072010
f[118]=78072010
f[119]=177901414
f[120]=177901414
f[121]=177901414
f[122]=177901414
f[123]=177901414
f[124]=177901414
f[125]=177901414
f[126]=177901414
f[127]=177901414
f[128]=177901414
f[129]=177901414
f[130]=177901414
f[131]=177901414
Total cost 168583741us
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-8 15:38:09 | 显示全部楼层
同9#结果不匹配,看来有BUG,谁来调试一下?我有事要出去了
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-8 18:42:45 | 显示全部楼层
找到一个bug,函数unmask中乘法可能会溢出,需要修改
  1. void unmask(int prime)
  2. {
  3.         int inv=HugeCalc::InvertMod(100,prime);
  4.         int u=prime-11;
  5.         while(u<0)u+=prime;
  6.         u=((long long)u*inv)%prime;
  7.         if(u*100+11!=prime){
  8.                 SET_BIT(u);
  9.         }
  10.         unsigned v=u+prime;
  11.         for(;v>prime;v+=prime){
  12.                 SET_BIT(v);
  13.         }
  14. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-8 18:46:19 | 显示全部楼层
修正以后的结果:
f[1]=1
f[2]=4
f[3]=4
f[4]=4
f[5]=10
f[6]=43
f[7]=43
f[8]=145
f[9]=145
f[10]=145
f[11]=361
f[12]=361
f[13]=361
f[14]=361
f[15]=448
f[16]=448
f[17]=652
f[18]=652
f[19]=652
f[20]=652
f[21]=4347
f[22]=5605
f[23]=6217
f[24]=6217
f[25]=6217
f[26]=6217
f[27]=8083
f[28]=8083
f[29]=8083
f[30]=8083
f[31]=8083
f[32]=8452
f[33]=8452
f[34]=8452
f[35]=23284
f[36]=23284
f[37]=23284
f[38]=23284
f[39]=23284
f[40]=23284
f[41]=23284
f[42]=44875
f[43]=44875
f[44]=46711
f[45]=80101
f[46]=80101
f[47]=80101
f[48]=80101
f[49]=80101
f[50]=417643
f[51]=417643
f[52]=417643
f[53]=417643
f[54]=417643
f[55]=417643
f[56]=417643
f[57]=417643
f[58]=417643
f[59]=417643
f[60]=417643
f[61]=417643
f[62]=417643
f[63]=417643
f[64]=417643
f[65]=1239046
f[66]=1239046
f[67]=1239046
f[68]=1239046
f[69]=1239046
f[70]=1239046
f[71]=5585445
f[72]=5585445
f[73]=5585445
f[74]=5585445
f[75]=5585445
f[76]=12264717
f[77]=12264717
f[78]=12264717
f[79]=13991758
f[80]=13991758
f[81]=16775473
f[82]=16775473
f[83]=17946187
f[84]=17946187
f[85]=17946187
f[86]=17946187
f[87]=17946187
f[88]=17946187
f[89]=17946187
f[90]=17946187
f[91]=17946187
f[92]=17946187
f[93]=17946187
f[94]=17946187
f[95]=30804307
f[96]=30804307
f[97]=30804307
f[98]=30804307
f[99]=30804307
f[100]=30804307
f[101]=75839734
f[102]=75839734
f[103]=75839734
f[104]=75839734
f[105]=75839734
f[106]=75839734
f[107]=78072010
f[108]=78072010
f[109]=78072010
f[110]=78072010
f[111]=78072010
f[112]=78072010
f[113]=78072010
f[114]=78072010
f[115]=78072010
f[116]=78072010
f[117]=78072010
f[118]=78072010
f[119]=177901414
f[120]=177901414
f[121]=177901414
f[122]=177901414
f[123]=177901414
f[124]=177901414
f[125]=177901414
f[126]=177901414
f[127]=177901414
f[128]=177901414
f[129]=177901414
f[130]=177901414
f[131]=177901414
f[132]=554979631
f[133]=554979631
f[134]=648847533
f[135]=648847533
f[136]=648847533
f[137]=648847533
f[138]=648847533
f[139]=648847533
f[140]=648847533
f[141]=648847533
f[142]=648847533
f[143]=648847533
f[144]=648847533
f[145]=648847533
f[146]=648847533
f[147]=648847533
f[148]=648847533
f[149]=648847533
f[150]=3539248351
f[151]=3539248351
f[152]=3539248351
f[153]=3539248351
f[154]=3539248351
f[155]=3539248351
f[156]=3539248351
f[157]=3539248351
f[158]=3539248351
f[159]=3539248351
f[160]=3539248351
f[161]=3539248351
f[162]=3539248351
f[163]=3539248351
f[164]=3539248351
f[165]=3539248351
f[166]=3539248351
f[167]=3539248351
f[168]=3539248351
f[169]=3539248351
f[170]=3539248351
Total cost 213745877us
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

056254628
 楼主| 发表于 2009-10-8 22:22:31 | 显示全部楼层
本帖最后由 056254628 于 2009-10-8 22:24 编辑

mathe的程序是不是还有Bug？
m<=49的结果和我的一样。但是我算出的：
f(51)=175623   f(54)=220659
---------------------------------------
比mathe的小很多。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-9 13:30:08 | 显示全部楼层
的确,如下修改:>改为>=
  1. void unmask(int prime)
  2. {
  3.         int inv=HugeCalc::InvertMod(100,prime);
  4.         int u=prime-11;
  5.         while(u<0)u+=prime;
  6.         u=((long long)u*inv)%prime;
  7.         if(u*100+11!=prime){
  8.                 SET_BIT(u);
  9.         }
  10.         unsigned v=u+prime;
  11.         for(;v>=prime;v+=prime){
  12.                 SET_BIT(v);
  13.         }
  14. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-9 13:33:18 | 显示全部楼层
Total num prime 53225,
Total prime masked,1691
f[1]=1
f[2]=4
f[3]=4
f[4]=4
f[5]=10
f[6]=43
f[7]=43
f[8]=145
f[9]=145
f[10]=145
f[11]=361
f[12]=361
f[13]=361
f[14]=361
f[15]=448
f[16]=448
f[17]=652
f[18]=652
f[19]=652
f[20]=652
f[21]=4347
f[22]=5605
f[23]=6217
f[24]=6217
f[25]=6217
f[26]=6217
f[27]=8083
f[28]=8083
f[29]=8083
f[30]=8083
f[31]=8083
f[32]=8452
f[33]=8452
f[34]=8452
f[35]=23284
f[36]=23284
f[37]=23284
f[38]=23284
f[39]=23284
f[40]=23284
f[41]=23284
f[42]=44875
f[43]=44875
f[44]=46711
f[45]=80101
f[46]=80101
f[47]=80101
f[48]=80101
f[49]=80101
f[50]=175623
f[51]=175623
f[52]=220659
f[53]=220659
f[54]=220659
f[55]=357075
f[56]=357075
f[57]=357075
f[58]=357075
f[59]=357075
f[60]=357075
f[61]=357075
f[62]=357075
f[63]=357075
f[64]=357075
f[65]=357075
f[66]=1239046
f[67]=1239046
f[68]=1239046
f[69]=1239046
f[70]=1239046
f[71]=4225245
f[72]=4225245
f[73]=4225245
f[74]=4225245
f[75]=4225245
f[76]=4225245
f[77]=4225245
f[78]=4225245
f[79]=4242612
f[80]=4242612
f[81]=4242612
f[82]=4242612
f[83]=4242612
f[84]=4242612
f[85]=4242612
f[86]=4242612
f[87]=4242612
f[88]=4242612
f[89]=4242612
f[90]=4242612
f[91]=4242612
f[92]=4242612
f[93]=4242612
f[94]=4242612
f[95]=4242612
f[96]=4242612
f[97]=4242612
f[98]=4242612
f[99]=7135851
f[100]=23717773
f[101]=23717773
f[102]=23717773
f[103]=23717773
f[104]=23717773
f[105]=23717773
f[106]=23717773
f[107]=23717773
f[108]=23717773
f[109]=23717773
f[110]=23717773
f[111]=23717773
f[112]=23717773
f[113]=23717773
f[114]=23717773
f[115]=23717773
f[116]=23717773
f[117]=23717773
f[118]=23717773
f[119]=23717773
f[120]=23717773
f[121]=23717773
f[122]=23717773
f[123]=23717773
f[124]=23717773
f[125]=167369311
f[126]=167369311
f[127]=167369311
f[128]=167369311
f[129]=167369311
f[130]=167369311
f[131]=167369311
f[132]=167369311
f[133]=167369311
f[134]=167369311
f[135]=167369311
f[136]=167369311
f[137]=167369311
f[138]=167369311
f[139]=167369311
f[140]=167369311
f[141]=167369311
f[142]=167369311
f[143]=167369311
f[144]=339898777
f[145]=339898777
f[146]=339898777
f[147]=339898777
f[148]=339898777
f[149]=339898777
f[150]=339898777
f[151]=339898777
f[152]=339898777
f[153]=339898777
f[154]=339898777
f[155]=339898777
f[156]=339898777
f[157]=339898777
f[158]=1307096556
f[159]=1307096556
f[160]=1307096556
f[161]=1307096556
f[162]=1307096556
f[163]=1307096556
f[164]=1307096556
f[165]=1307096556
f[166]=1550482953
f[167]=1550482953
f[168]=1550482953
f[169]=1550482953
f[170]=1550482953
f[171]=3539248312
f[172]=3539248312
f[173]=3539248312
f[174]=3539248312
f[175]=3539248312
f[176]=3539248312
f[177]=3539248312
f[178]=3539248312
f[179]=3539248312
f[180]=3539248312
f[181]=3539248312
f[182]=3539248312
f[183]=3539248312
f[184]=3539248312
f[185]=3539248312
f[186]=3539248312
f[187]=3539248312
f[188]=3539248312
f[189]=3539248312
f[190]=3539248312
f[191]=3539248312
f[192]=3539248312
f[193]=3539248312
f[194]=3539248312
f[195]=3539248312
f[196]=3539248312
f[197]=3539248312
f[198]=3539248312
f[199]=3539248312
f[200]=3539248312
f[201]=3539248312
f[202]=3539248312
f[203]=3539248312
f[204]=3539248312
f[205]=3539248312
f[206]=3539248312
f[207]=3539248312
f[208]=3539248312
f[209]=3539248312
Total cost 183552557us
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-9 14:44:38 | 显示全部楼层
[100]=30804307?
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2009-10-9 14:53:01 | 显示全部楼层
mathe 的结果是对的。[100]=23717773
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-27 07:26 , Processed in 0.045484 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表