连续100个整数末尾加上11后都是合数 - 第2页 - 编程擂台 - 数学研发论坛

mathe 发表于 2009-10-8 15:33:06

贴一段使用了HugeCalc的代码(其实就是为了求素数和数论倒数的代码)
#define BUF_LEN (1<<27)
#define MAX_PRIME 655360
int mask;
unsigned plist;
int pc;
#define GETWORD(x)((x)>>5)
#define GETOFF(x) ((x)&31)
#define OFFBIT(x) (1<<GETOFF(x))
#define SET_BIT(x)(mask|=OFFBIT(x))
#define TEST_BIT(x) ((mask&OFFBIT(x))!=0)
void unmask(int prime)
{
int inv=HugeCalc::InvertMod(100,prime);
int u=prime-11;
while(u<0)u+=prime;
u*=inv;
u%=prime;
if(u*100+11!=prime){
SET_BIT(u);
}
unsigned v=u+prime;
for(;v>prime;v+=prime){
SET_BIT(v);
}
}

void check_list()
{
int cur_len=0;
int max_len=0;
unsigned v=0;
do{
if(TEST_BIT(v)){
cur_len++;
if(cur_len>max_len){
printf("f[%d]=%u\n",cur_len,v-cur_len+1);
max_len=cur_len;
}
}else{
cur_len=0;
}
}while(++v!=0);
}

int main()
{
HugeCalc::EnableTimer();
pc=HugeCalc::GetPrimeList(plist,MAX_PRIME,7,MAX_PRIME);
unmask(3);
unsigned timer=HugeCalc::GetTimer();
int i;
printf("Total num prime %d, %dus\n",pc,timer);
for(i=0;i<pc;i++){
unmask(plist);
if(i%100==99){
timer=HugeCalc::GetTimer();
}
}
timer=HugeCalc::GetTimer();
printf("Total prime masked,%dus\n",timer);
check_list();
timer=HugeCalc::GetTimer();
printf("Total cost %dus\n",timer);
}
可以计算到f(131)

mathe 发表于 2009-10-8 15:36:23

f=1
f=4
f=4
f=4
f=4
f=43
f=43
f=145
f=145
f=145
f=145
f=145
f=145
f=145
f=145
f=145
f=652
f=652
f=652
f=652
f=4347
f=4902
f=4902
f=5248
f=5248
f=5248
f=8083
f=8083
f=8083
f=8083
f=8083
f=8083
f=8083
f=8083
f=8083
f=8083
f=8083
f=38335
f=44875
f=44875
f=44875
f=44875
f=44875
f=46711
f=51481
f=51481
f=80101
f=80101
f=80101
f=223312
f=223312
f=223312
f=223312
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=1239046
f=1239046
f=1239046
f=1239046
f=1239046
f=1239046
f=1767661
f=3848451
f=4157752
f=4157752
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=4543498
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=5346948
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
Total cost 168583741us

mathe 发表于 2009-10-8 15:38:09

同9#结果不匹配,看来有BUG,谁来调试一下?我有事要出去了

mathe 发表于 2009-10-8 18:42:45

找到一个bug,函数unmask中乘法可能会溢出,需要修改void unmask(int prime)
{
int inv=HugeCalc::InvertMod(100,prime);
int u=prime-11;
while(u<0)u+=prime;
u=((long long)u*inv)%prime;
if(u*100+11!=prime){
SET_BIT(u);
}
unsigned v=u+prime;
for(;v>prime;v+=prime){
SET_BIT(v);
}
}

mathe 发表于 2009-10-8 18:46:19

修正以后的结果:
f=1
f=4
f=4
f=4
f=10
f=43
f=43
f=145
f=145
f=145
f=361
f=361
f=361
f=361
f=448
f=448
f=652
f=652
f=652
f=652
f=4347
f=5605
f=6217
f=6217
f=6217
f=6217
f=8083
f=8083
f=8083
f=8083
f=8083
f=8452
f=8452
f=8452
f=23284
f=23284
f=23284
f=23284
f=23284
f=23284
f=23284
f=44875
f=44875
f=46711
f=80101
f=80101
f=80101
f=80101
f=80101
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=417643
f=1239046
f=1239046
f=1239046
f=1239046
f=1239046
f=1239046
f=5585445
f=5585445
f=5585445
f=5585445
f=5585445
f=12264717
f=12264717
f=12264717
f=13991758
f=13991758
f=16775473
f=16775473
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=17946187
f=30804307
f=30804307
f=30804307
f=30804307
f=30804307
f=30804307
f=75839734
f=75839734
f=75839734
f=75839734
f=75839734
f=75839734
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=78072010
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=177901414
f=554979631
f=554979631
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=648847533
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=3539248351
f=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

的确,如下修改:>改为>=void unmask(int prime)
{
   int inv=HugeCalc::InvertMod(100,prime);
   int u=prime-11;
   while(u<0)u+=prime;
   u=((long long)u*inv)%prime;
   if(u*100+11!=prime){
            SET_BIT(u);
   }
   unsigned v=u+prime;
   for(;v>=prime;v+=prime){
            SET_BIT(v);
   }
}

mathe 发表于 2009-10-9 13:33:18

Total num prime 53225,
Total prime masked,1691
f=1
f=4
f=4
f=4
f=10
f=43
f=43
f=145
f=145
f=145
f=361
f=361
f=361
f=361
f=448
f=448
f=652
f=652
f=652
f=652
f=4347
f=5605
f=6217
f=6217
f=6217
f=6217
f=8083
f=8083
f=8083
f=8083
f=8083
f=8452
f=8452
f=8452
f=23284
f=23284
f=23284
f=23284
f=23284
f=23284
f=23284
f=44875
f=44875
f=46711
f=80101
f=80101
f=80101
f=80101
f=80101
f=175623
f=175623
f=220659
f=220659
f=220659
f=357075
f=357075
f=357075
f=357075
f=357075
f=357075
f=357075
f=357075
f=357075
f=357075
f=357075
f=1239046
f=1239046
f=1239046
f=1239046
f=1239046
f=4225245
f=4225245
f=4225245
f=4225245
f=4225245
f=4225245
f=4225245
f=4225245
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=4242612
f=7135851
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=23717773
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=167369311
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=339898777
f=1307096556
f=1307096556
f=1307096556
f=1307096556
f=1307096556
f=1307096556
f=1307096556
f=1307096556
f=1550482953
f=1550482953
f=1550482953
f=1550482953
f=1550482953
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
f=3539248312
Total cost 183552557us

〇〇发表于 2009-10-9 14:44:38

=30804307?

gxqcn 发表于 2009-10-9 14:53:01

mathe 的结果是对的。=23717773

页: 1 [2] 3 4

数学研发论坛's Archiver