能力值：
( LV5，RANK：60 )
|
-
-
2 楼
可以再优化一下，比如除2外偶数可以直接无视，一个素数p可以直接从p的平方开始标记
|
能力值：
( LV5，RANK：60 )
|
-
-
3 楼
教科书上是：
if( table[k] == 0 )
{
for( long j=k+k; j< NUM; j+=k)
{
table[j] = 1;//若为合数，数值变为1
}
}
|
能力值：
( LV4，RANK：40 )
|
-
-
4 楼
空间上也没有省太多。一般编译器仍然把bool用1byte而不是bite。
实测这个程序在VC9下编译运行内存是49M
要高效的话还是内联汇编把。不过移植性差。
|
能力值：
( LV5，RANK：60 )
|
-
-
5 楼
其实这种方法就是要空间换时间，计算机并不支持位的复杂运算，即使支持，运行时间反而更多，因此编译器根据计算机的编译成字节或更大的单位空间，是可以理解的，而这编译结果正是这种算法能够快速的原因之一，而且没有乘除运算。
|
能力值：
( LV4，RANK：40 )
|
-
-
6 楼
如果不顾及空间只为了速度。稍作了一下优化
但是感觉空间浪费还是有点过。有15/16的空间没用。
#include "stdio.h"
#include "math.h"
#define NUM 5000
void suShu()
{
bool* table = new bool[NUM+1];
//int numbers = 0;
for([COLOR="Red"]register [/COLOR]long [COLOR="Red"]i=1[/COLOR]; i<=NUM; [COLOR="red"]i++,i++)[/COLOR]
{
table[i] = 0;//初始化数组
}
long halfNum = (long)sqrt(NUM);//因数最大值
for([COLOR="Red"]register[/COLOR] long [COLOR="red"]k=3[/COLOR]; k<=halfNum; [COLOR="red"]k++,k++ )[/COLOR] {
if( table[k] == 0 )
{
long l = NUM/k;
for( long [COLOR="red"]j=3;[/COLOR] j<= l; [COLOR="red"]j++,j++)[/COLOR] {
table[k*j] = 1;//若为合数，数值变为1
}
}
}
[COLOR="red"] printf("%12d",2);[/COLOR]
for([COLOR="Red"]register [/COLOR]long [COLOR="red"]l=3; [/COLOR]l<=NUM;[COLOR="red"] l++,l++)[/COLOR] {
if(table[l] == 0)
{
//numbers++;
printf("%12d",l);
}
}
}
int main()
{
suShu();
return 0;
}
|
能力值：
( LV4，RANK：40 )
|
-
-
7 楼
AsmDebuger
的写法优化就是
if( table[k] == 0 )
{
for( long j=k+k+k; j< NUM; j+=k+k)
{
table[j] = 1;//若为合数，数值变为1
}
}
|
能力值：
( LV5，RANK：60 )
|
-
-
8 楼
void FindPrime()
{
int i=3,j,k,step;
k=sqrt(MAX_SIZE);
while(i<=k)
{
if(p[i]==0)
{
step=i<<1;
for(j=i*i;j<=MAX_SIZE;j+=step)
p[j]=1;
}
i+=2;
}
}
|
|
|
