尋找 1 到指定正整數之間所有的質數--Using C by 梵听版-密码应用-看雪-安全社区|安全招聘|kanxue.com

最新回复 (7)
erex 雪币： 171 活跃值： (10) 能力值： ( LV5，RANK：60 ) 在线值：发帖 9 回帖 57 粉丝 0 关注私信	erex 1 2009-6-29 23:04 2 楼 0 可以再优化一下，比如除2外偶数可以直接无视，一个素数p可以直接从p的平方开始标记
AsmDebuger 雪币： 1270 活跃值： (104) 能力值： ( LV5，RANK：60 ) 在线值：发帖 8 回帖 359 粉丝 1 关注私信	AsmDebuger 1 2009-6-30 08:26 3 楼 0 教科书上是： if( table[k] == 0 ) { for( long j=k+k; j< NUM; j+=k) { table[j] = 1;//若为合数，数值变为1 } }
Yangs 雪币： 164 活跃值： (10) 能力值： ( LV4，RANK：40 ) 在线值：发帖 6 回帖 62 粉丝 2 关注私信	Yangs 2009-6-30 11:04 4 楼 0 空间上也没有省太多。一般编译器仍然把bool用1byte而不是bite。实测这个程序在VC9下编译运行内存是49M 要高效的话还是内联汇编把。不过移植性差。
AsmDebuger 雪币： 1270 活跃值： (104) 能力值： ( LV5，RANK：60 ) 在线值：发帖 8 回帖 359 粉丝 1 关注私信	AsmDebuger 1 2009-6-30 15:11 5 楼 0 其实这种方法就是要空间换时间，计算机并不支持位的复杂运算，即使支持，运行时间反而更多，因此编译器根据计算机的编译成字节或更大的单位空间，是可以理解的，而这编译结果正是这种算法能够快速的原因之一，而且没有乘除运算。
Yangs 雪币： 164 活跃值： (10) 能力值： ( LV4，RANK：40 ) 在线值：发帖 6 回帖 62 粉丝 2 关注私信	Yangs 2009-6-30 16:40 6 楼 0 如果不顾及空间只为了速度。稍作了一下优化但是感觉空间浪费还是有点过。有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; }
Yangs 雪币： 164 活跃值： (10) 能力值： ( LV4，RANK：40 ) 在线值：发帖 6 回帖 62 粉丝 2 关注私信	Yangs 2009-6-30 16:48 7 楼 0 AsmDebuger 的写法优化就是 if( table[k] == 0 ) { for( long j=k+k+k; j< NUM; j+=k+k) { table[j] = 1;//若为合数，数值变为1 } }
erex 雪币： 171 活跃值： (10) 能力值： ( LV5，RANK：60 ) 在线值：发帖 9 回帖 57 粉丝 0 关注私信	erex 1 2009-6-30 17:43 8 楼 0 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; } }
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

erex

雪币： 171

活跃值： (10)

能力值：

( LV5，RANK：60 )

在线值：

发帖

9

回帖

57

粉丝

0

关注

私信

erex 1 2009-6-29 23:04: 2 楼
0

可以再优化一下，比如除2外偶数可以直接无视，一个素数p可以直接从p的平方开始标记

AsmDebuger

雪币： 1270

活跃值： (104)

能力值：

( LV5，RANK：60 )

在线值：

发帖

8

回帖

359

粉丝

1

关注

私信

AsmDebuger 1 2009-6-30 08:26: 3 楼
0

教科书上是：
if( table[k] == 0 )
{
   for( long j=k+k; j< NUM; j+=k)
   {
      table[j] = 1;//若为合数，数值变为1
   }
}

Yangs

雪币： 164

活跃值： (10)

能力值：

( LV4，RANK：40 )

在线值：

发帖

6

回帖

62

粉丝

2

关注

私信

Yangs 2009-6-30 11:04: 4 楼
0

空间上也没有省太多。一般编译器仍然把bool用1byte而不是bite。
实测这个程序在VC9下编译运行内存是49M
要高效的话还是内联汇编把。不过移植性差。

AsmDebuger

雪币： 1270

活跃值： (104)

能力值：

( LV5，RANK：60 )

在线值：

发帖

8

回帖

359

粉丝

1

关注

私信

AsmDebuger 1 2009-6-30 15:11: 5 楼
0

其实这种方法就是要空间换时间，计算机并不支持位的复杂运算，即使支持，运行时间反而更多，因此编译器根据计算机的编译成字节或更大的单位空间，是可以理解的，而这编译结果正是这种算法能够快速的原因之一，而且没有乘除运算。

Yangs

雪币： 164

活跃值： (10)

能力值：

( LV4，RANK：40 )

在线值：

发帖

6

回帖

62

粉丝

2

关注

私信

Yangs 2009-6-30 16:40: 6 楼
0

如果不顾及空间只为了速度。稍作了一下优化

但是感觉空间浪费还是有点过。有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;
}

Yangs

雪币： 164

活跃值： (10)

能力值：

( LV4，RANK：40 )

在线值：

发帖

6

回帖

62

粉丝

2