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

xiaozhu2007

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

答案：
int findvalue[2000]={2};
static int find=1;
bool adjust(int value)
{
assert(value>=2);
if(value==2) return true;
for(int i=0;i<=find;i++)
{
if(value%findvalue==0)
return false;
}
findvalue[find++];
return true;
}

没看明白,谁给讲讲,3ks!

su_787910081

楼主不是已经有了代码了吗?
他的意思不是说没弄明白那代码是怎么来的吗?
怎么全都自己另外去写了啊.  
楼主的那个算法非常地道啊.  
我做了一些改动.

#include <stdio.h>
#include <assert.h>

static int findvalue[2000] = {2}; // 2是偶数, 但是素数.所以把他直接放进去,提高一下效率
static int ind=1;                        //  这个是下标,  下一个素数放在  findvalue[ind]   里面
void prime(int value);                 //  函数声明   判断  value 是不是素数, 如果是放到数组里

int main()
{
        int  i=3;
        while(i<=2000){
                 prime(i);
                 i  +=  2;
        }

        //将数组里面的素数打印出来, 每10个换一行
        for(i=0;  i<ind;  i++){
                  printf("%4d ",  findvalue);
                  if((i+1)%10  ==  0) {  printf("\n");  }
        }
        return 0;
}

         /************************************************
           *    下面那个函数就是判断传入的参数是否是素数,   
           *    只要这个参数被现在数组里的任一一个素数整除,   
           *    则说明他不是素数;   
           *    反之, 说明他就是素数.   
           *    既然是素数就把它放到数组里.   
           *    ind  是下标, 同时它还记录了这个数组里一共存放了多少个素数.
           ***********************************************/
void   prime( int   value){
          assert( value>2);
          int  i;

          for( i=0;  i<ind;  i++){
                    if(value%findvalue == 0) { return ;}
          }
          findvalue[ind++] = value;
}

cokeboL

回复 34# sacry


    看了下介绍，刚好我的代码就用的这个方法，俺是文科，以前没碰到过这，嘿嘿

_Rayx

传说中的打表。

cokeboL

回复 34# sacry


    3ks~

sacry

回复 32# cokeboL

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation

他们说的是这个。

   

dengxiayehu

xiaozhu2007 发表于 2008-09-20 20:16
求2~2000的所有素数.有足够的内存,要求尽量快

答案：

楼主，你的答案我也没整明白

cokeboL

而且楼上大部分说查表的人都没仔细理解题目，说找到2000以内所有的，他们都是找到一个，题目没回答全。

即使是用查表，只要生成素数表，非素数的没必要放到里面；然后通过二分查找之类的找到素数表内的下标范围，然后取出来才是最终答案。

〇〇

ytl 发表于 2008-09-22 10:30
既然承认最关键是建表，所以不能用查表法。
2000个数不是关键，因为这只是算法题而已，考的是算法。如 ...

直接拿来用最快

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. }
    

复制代码