[原創(chuàng)] 靜態(tài)質(zhì)數(shù)表生成函數(shù)

haoji

判斷一個(gè)數(shù)是否是質(zhì)數(shù)，經(jīng)過(guò)實(shí)驗(yàn)，即使在2千萬(wàn)的范圍內(nèi)，還是查表的速度更快，占用內(nèi)存也不多，即使2千萬(wàn)的位序列也不過(guò)占2M左右的內(nèi)存。

寫(xiě)了一個(gè)程序，自動(dòng)生成一個(gè)靜態(tài)表函數(shù)。

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <limits.h>
   
5. #include <math.h>
   
6. 
   
7. int main(int argc, char** argv)
   
8. {
   
9.   int total=2000;
   
10.   int cols=6;
    
11.   int myjs=1;
    
12.   
    
13.   if(argc>2)
    
14.   {
    
15.      fprintf(stderr,"Usage:%s total\n",argv[0]);
    
16.      return -1;
    
17.   }
    
18.   else if(argc==2)
    
19.      total=(int)strtol(argv[1],NULL,10);
    
20.   
    
21. 
    
22.   int js=3;
    
23.   int i;
    
24.   int t;
    
25. 
    
26.   printf("int myadjust(int shu)\n\
    
27. {\n\
    
28.     assert(shu<=%d);\n\
    
29.     const static unsigned int mytable[]={\n\
    
30.             ",total);
    
31. 
    
32.   unsigned int output=0x60000000;
    
33. 
    
34.   for(t=3;t<=total;t++)
    
35.   {
    
36.     int k=(int)(sqrt(t));
    
37.     if(t%2==0)
    
38.       i=0;
    
39.     else
    
40.       for(i=3;i<=k;i+=2)
    
41.        if(t%i==0)
    
42.           break;
    
43.     if(i>k)
    
44.       output|=(0x80000000 >> (js & 0x1F));
    
45.    
    
46.     if((js & 0x1F) == 31)
    
47.     {
    
48.       printf("0x%X,",output);
    
49.       output=0;
    
50.       if(myjs++ % cols ==0)
    
51.         printf("\n\
    
52.             ");
    
53.     }
    
54.    
    
55.     js++;
    
56.   }
    
57. 
    
58.   if((--js & 0x1F) != 31)
    
59.     printf("0x%X\n",output);  
    
60. 
    
61.   printf("    };\n\n    return (mytable[shu >> 5] & ((unsigned int)0x80000000 >> (shu & 0x1F)));\n}\n");
    
62. 
    
63.   return 0;
    
64. }
    
65. 
    

復(fù)制代碼

比如生成的0-2000范圍內(nèi)的質(zhì)數(shù)表函數(shù)（內(nèi)置位序列，0為false，非0為true，判斷質(zhì)數(shù)）：

1. 
   
2. 
   
3. int myadjust(int shu)
   
4. {
   
5.     assert(shu<=2000);
   
6.     const static unsigned int mytable[]={
   
7.             0x75145105,0x4510414,0x11411040,0x45144001,0x10500504,0x11041401,
   
8.             0x45001001,0x14414010,0x41050450,0x4001144,0x104014,0x41010411,
   
9.             0x4044040,0x14014110,0x40451001,0x1101104,0x500004,0x10041050,
   
10.             0x40104141,0x4500100,0x51041400,0x44101004,0x4010104,0x11010440,
    
11.             0x44001004,0x500514,0x1000451,0x45100,0x110100,0x40441040,
    
12.             0x1104101,0x4004414,0x1410050,0x5040001,0x14410404,0x10400001,
    
13.             0x40101004,0x10404004,0x41050400,0x40100005,0x10504510,0x1410000,
    
14.             0x4104,0x4000100,0x40011441,0x1141001,0x514410,0x1001010,
    
15.             0x1044101,0x10110004,0x41441410,0x4000041,0x14000004,0x50040050,
    
16.             0x4041041,0x4114,0x401001,0x1000100,0x4114500,0x40041040,
    
17.             0x140005,0x410,0x10450000
    
18.     };
    
19. 
    
20.     return (mytable[shu >> 5] & ((unsigned int)0x80000000 >> (shu & 0x1F)));
    
21. }
    
22. 
    
23. 
    

復(fù)制代碼

[ 本帖最后由 haoji 于 2008-9-22 19:12 編輯 ]

Godbach

好東西，有時(shí)間測(cè)試一下。
BTW，代碼里怎么那么多\n啊

haoji

原帖由 Godbach 于 2008-9-22 19:29 發(fā)表
好東西，有時(shí)間測(cè)試一下。
BTW，代碼里怎么那么多\n啊

為了美觀，

謝謝鼓勵(lì)

Godbach

呵呵，都是包含在printf里面。

black_billow08

恩，不錯(cuò)，我來(lái)學(xué)習(xí)一下哦，呵呵呵

redspider

費(fèi)勁啊，為什么不用 bitset

RobinHoo

什么跟什么呀。看不出快在那里？

haoji

原帖由 redspider 于 2008-9-23 09:44 發(fā)表
費(fèi)勁啊，為什么不用 bitset

費(fèi)勁嗎？一行語(yǔ)句還費(fèi)勁？

haoji

原帖由 RobinHoo 于 2008-9-23 12:12 發(fā)表
什么跟什么呀�？床怀隹煸谀抢铮�

沒(méi)實(shí)驗(yàn)過(guò)就別亂說(shuō)

aobai

老大，能否注釋下，照顧下我們