[原创] 静态质数表生成函数

haoji

判断一个数是否是质数，经过实验，即使在2千万的范围内，还是查表的速度更快，占用内存也不多，即使2千万的位序列也不过占2M左右的内存。

写了一个程序，自动生成一个静态表函数。

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. 
    

复制代码

比如生成的0-2000范围内的质数表函数（内置位序列，0为false，非0为true，判断质数）：

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. 
    

复制代码

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

Godbach

好东西，有时间测试一下。
BTW，代码里怎么那么多\n啊

haoji

原帖由 Godbach 于 2008-9-22 19:29 发表
好东西，有时间测试一下。
BTW，代码里怎么那么多\n啊

为了美观，

谢谢鼓励

Godbach

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

black_billow08

恩，不错，我来学习一下哦，呵呵呵

redspider

费劲啊，为什么不用 bitset

RobinHoo

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

haoji

原帖由 redspider 于 2008-9-23 09:44 发表
费劲啊，为什么不用 bitset

费劲吗？一行语句还费劲？

haoji

原帖由 RobinHoo 于 2008-9-23 12:12 发表
什么跟什么呀。看不出快在那里？

没实验过就别乱说

aobai

老大，能否注释下，照顾下我们