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

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 连续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-11-22 13:21 , Processed in 0.025076 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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