求2~2000的所有素数.有足够的内存,要求尽量快

ytl

原帖由 haoji 于 2008-9-22 00:06 发表
看来，在百万以内的数字范围，查表法比其他方法效率要高。


甚至在64位大内存系统上面，在上亿范围的数字内，查表永远效率最高。

跑题了，因为题目是要找出2000以内所有的素数，实际上考的就是生成这样一张表的算法

haoji

原帖由 ytl 于 2008-9-22 00:20 发表


跑题了，因为题目是要找出2000以内所有的素数，实际上考的就是生成这样一张表的算法

如果为了建立表，2000以内质数的搜索的算法没有必要被讨论，用最笨的搜索法也没关系，时间也不会差到1毫秒。
最关键还是如何方便地建立表，和高效地使用表。
没必要因为楼主的题目而限制了思维。

ytl

原帖由 haoji 于 2008-9-22 10:23 发表


如果为了建立表，2000以内质数的搜索的算法没有必要被讨论，用最笨的搜索法也没关系，时间也不会差到1毫秒。
最关键还是如何方便地建立表，和高效地使用表。
没必要因为楼主的题目而限制了思维。

既然承认最关键是建表，所以不能用查表法。
2000个数不是关键，因为这只是算法题而已，考的是算法。如果不是考察算法，确实没必要被讨论，相信很多数学家早就手工计算过了，直接拿来用就是了，为什么要编程序用计算机搜索？

[ 本帖最后由 ytl 于 2008-9-22 10:40 编辑 ]

guohua219

很好的贴子,来学习

xwolff

#include <stdio.h>
#include <math.h>

#define N 2000

void main(void)
{
        int i, j, cnt, tag; // tag变量是用来判断是否素数的标志
        int a[N]; // 开辟数组，存放素数

        a[0] = 2;       
        cnt = 1;
        // 除2以外，所有的素数都是奇数，因此从3开始，可以减少一半的计算量。
        for ( i = 3; i < N; i += 2)
        {
                tag = 1;
                for ( j = 2; j <= sqrt(i); j++ )
                {
                        if ( i%j == 0 )
                        {
                                tag = 0;
                                break;
                        }
                }
                if ( tag ) a[cnt++] = i;

        }

        printf("%d以内的素数(共计%d个)如下：\n", N, cnt);
        for ( i = 0; i < cnt; i++ )
        {
                printf("%-6d", a);
                if ( (i+1)%10 == 0 ) printf("\n");
        }
        printf("\n]");

}

xwolff

编程就得务实，理论很抽象，实践是最要的。再快的算法，也得逐个判断，这是必须的。计算机是机器不是人，怎么做得我们告诉它，自己能做的千万别交给机器去做，程序员实在做不了的再交给机器做，一定能求解出最优算法。

lonecrystal

筛法选素数.

kycgjy

for(int i=0;i<=find;i++)
应该改为i<find。
另外最好不要用find吧，在C/C++里有find函数，这样在for里面会觉得“模糊”。

cokeboL

查表是神马。。

cokeboL

楼主给的答案明显是错误代码，我写了个不用查表的：

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <stdlib.h>
   
4. #include <unistd.h>
   
5. #include <math.h>
   
6. 
   
7. char is_prime(int n)
   
8. {
   
9.     int i=2;
   
10.     if(2 == n)
    
11.         return 1;
    
12.     while(i < sqrt(n)){
    
13.         if(!(n % i))
    
14.             return 0;
    
15.         i++;
    
16.     }
    
17. 
    
18.     return 1;
    
19. }
    
20. 
    
21. void find_prime(int max)
    
22. {
    
23.     int i, j, tmp;
    
24.     char *p = (char*)calloc(max, 1);
    
25.     p[0] = -1;
    
26.     for(i = 2; i <= max; i++){
    
27.         if(-1 == p[i-1]){
    
28.             continue;
    
29.         }
    
30.         if(is_prime(i)){
    
31.             for(j = 2; (tmp = i * j) <= max; j++){
    
32.                 p[tmp-1] = -1;
    
33.             }
    
34.         }
    
35.     }
    
36.     j = 0;
    
37.     for(i = 2; i <= max; i++){
    
38.         if(p[i-1] != -1){
    
39.             printf("%10d%c", i, (0==(++j%10))?'\n':' ');
    
40.         }
    
41.     }
    
42.     printf("\n");
    
43.     free(p);
    
44. }
    
45. 
    
46. int main(int argc, char *argv[])
    
47. {
    
48.     find_prime(atoi(argv[1]));
    
49.     return 0;
    
50. }
    

复制代码