求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!

萍水e相逢

调用 adjust( value) 函数，判断 value 是不是 素数；
value = 2 ，是，直接返回；
value 为 2 以外的，求 value 除 已知素数的 余数，只要有一个，余数为 0，即 整除，value 不是 素数；都不整除， value 即为素数，保存。

不过，似乎有误： findvalue[find++]; 应为 findvalue[find++] = value  ;

只是 现在无法 调试！

nbkjbo

筛子的方法

MMMIX

原帖由 nbkjbo 于 2008-9-20 20:52 发表
筛子的方法

不是这么叫的，应该是“筛法”

aliking

“有足够的内存,要求尽量快”，似乎应该用查表法，提前算好放到内存里。

cugb_cat

楼主google：筛法求素。。

cjaizss

筛法:
用awk写了一个

1. 
   
2. #!/bin/awk -f
   
3. {
   
4.         x=$1;
   
5.         for(i=3;i<=x;i+=2)
   
6.                 a[i]=1;
   
7.         y=int(sqrt($1));
   
8.         for(j=3;j<=x;j+=2) {
   
9.                 for(k=j+j;k<=x;k+=j){
   
10.                         a[k]=0;
    
11.                         t++;
    
12.                 }
    
13.         }
    
14.         printf("2 ");
    
15.         for(i=3;i<=x;i+=2)
    
16.                 if(a[i]==1)
    
17.                         printf("%d ",i);
    
18.         printf("\n");
    
19.         exit
    
20. }
    
21. 
    

复制代码

MMMIX

原帖由 cjaizss 于 2008-9-20 23:10 发表
筛法:
用awk写了一个

用 Haskell 写了一个：

1. 
   
2. sieve :: [Integer] -> [Integer]
   
3. sieve (x:xs) = x : sieve xs'
   
4.              where xs' = filter (\y -> y `mod` x /= 0) xs
   
5. 
   
6. primes = sieve $ 2:[3,5..]
   

复制代码

要得到小于 2000 的素数可用

1. 
   
2. takeWhile (< 2000) primes
   

复制代码

[ 本帖最后由 MMMIX 于 2008-9-21 00:28 编辑 ]

suraid

原帖由 aliking 于 2008-9-20 21:49 发表
“有足够的内存,要求尽量快”，似乎应该用查表法，提前算好放到内存里。

同意，2-2000,当然是用查表法最快了~

redspider

原帖由 aliking 于 2008-9-20 21:49 发表
“有足够的内存,要求尽量快”，似乎应该用查表法，提前算好放到内存里。

同意