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

〇〇

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

直接拿来用最快

cokeboL

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

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

dengxiayehu

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

答案：

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

sacry

回复 32# cokeboL

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

他们说的是这个。

   

cokeboL

回复 34# sacry


    3ks~

_Rayx

传说中的打表。

cokeboL

回复 34# sacry


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

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