• 找 1 到指定正整之所有的--Using C by 梵听版

引用:
 找 1 到指定正整之所有的.rar 

太慢了，我发一个我写的，求50000000内的素数，用3秒左右吧
不过是空间换时间……

代码:
#include "stdio.h"
#include "math.h"

#define NUM 50000000

void suShu()
{
  bool* table = new bool[NUM+1];
  //int numbers = 0;
  
  for( long i=0; i<=NUM; i++ )
  {
    table[i] = 0;//初始化数组
  }

  long halfNum = (long)sqrt(NUM);//因数最大值

  for( long k=2; k<=halfNum; k++ )
  {
    if( table[k] == 0 )
    {
      long l = NUM/k;
      for( long j=2; j<= l; j++)
      {
        table[k*j] = 1;//若为合数，数值变为1
      }
    }
  }

  for( long l=2; l<=NUM; l++)
  {
    if(table[l] == 0)
    {
      //numbers++;
      printf("%12d",l);
    }
  }
  
}

int main()
{
  suShu();
  
  return 0;
}

  • 标 题：答复
  • 作 者：Yangs
  • 时 间：2009-06-30 16:40:06

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

但是感觉空间浪费还是有点过。有15/16的空间没用。

代码:
#include "stdio.h"
#include "math.h"

#define NUM 5000

void suShu()
{
  bool* table = new bool[NUM+1];
  //int numbers = 0;
  
  for(register long i=1; i<=NUM; i++,i++)
  {
    table[i] = 0;//初始化数组
  }

  long halfNum = (long)sqrt(NUM);//因数最大值

  for(register long k=3; k<=halfNum; k++,k++ )  {
    if( table[k] == 0 )
    {
      long l = NUM/k;
      for( long j=3; j<= l; j++,j++)      {
        table[k*j] = 1;//若为合数，数值变为1
      }
    }
  }

  printf("%12d",2);
  for(register long l=3; l<=NUM; l++,l++)  {
    if(table[l] == 0)
    {
      //numbers++;
      printf("%12d",l);
    }
  }
  
}

int main()
{
  suShu();
  
  return 0;
}

  • 标 题：答复
  • 作 者：AsmDebuger
  • 时 间：2009-06-30 08:26:05

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

  • 标 题：答复
  • 作 者：Yangs
  • 时 间：2009-06-30 16:48:34

AsmDebuger  
的写法优化就是

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

  • 标 题：答复
  • 作 者：erex
  • 时 间：2009-06-30 17:43:11

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