C++ ,C 筛法求素数

素数"/>

C++ ,C 筛法求素数

自己没事,写的一个程序,筛法的原理:在n(n为求素数的范围)以内的数中,把2的倍数都去掉,再把3的倍数都去掉,如此,依次把第一个没有去掉数的倍数去掉,注意这个数本身不去掉.最后没被去掉的为所有的素数

#include "stdafx.h"
#include "string.h"
#include "math.h"
#include "windows.h"
#include "iostream.h"
#include "stdlib.h"
//一共有三个算法A B A2　其中A B　很慢，
//A2是改进型，速度很快，如不往屏幕输出　１亿内的质数在1.3秒内求出。
//B是用的是位操作，用内存少　因为没有优化，所以速度慢
class Prime
{
private:
 unsigned int  PrimeNum;
 char *buffer;
public: 
 Prime(long int num):PrimeNum(num){}
 void PrintPrimeNum();
 void PrintPrimeNumFor_A2();
 void Calculate_A();
 void Calculate_B();
 void Calculate_A2();
 ~Prime();

};

void Prime::Calculate_A()
{
 unsigned int length=PrimeNum/8+1;
 char MASKA,MASKB;
 register unsigned int i,j;
 _asm mov MASKA,10000000b
 _asm mov MASKB,10000000b
 buffer=new char[length];
 memset(buffer,0,length);
 for(i=2;i<=PrimeNum;i++)
 {
  if((buffer[i/8]&(MASKA>>(i%8)))==1)
  {   
   continue;
  }
  for(j=i+i;j<=PrimeNum;j+=i)
  {
      
    MASKB=MASKA>>(j%8);
    buffer[j/8]|=MASKB;
  }
 
 }
 
}

void Prime::Calculate_A2()
{
 unsigned int length=PrimeNum;
 register unsigned int i,j;
 buffer=new char[length+1];
 memset(buffer,0,length);
 for(i=2;i<=PrimeNum;i++)
 {
  if(buffer[i]==1) continue;
  
  for(j=i+i;j<=PrimeNum;j+=i)
  {

   buffer[j]=1;
  }
 
 }
 
}

void Prime::Calculate_B()
{
 unsigned int length=PrimeNum/8+1;
 char MASKA;
 bool isP=true;
 register unsigned int i,j,n;
 _asm mov MASKA,01000000b
 buffer=new char[length];
 memset(buffer,0,length);
 buffer[0]|=MASKA;
 for(i=2;i<PrimeNum;i++)
 {
  isP=true;
  _asm ror MASKA,1
  n=(int)sqrt(i);
  for(j=2;j<=n;j++)
  {
   if(i%j==0) isP=false;
  }
  if(!isP)
  {
   buffer[i/8]|=MASKA;

  }

 }
 
}

void Prime::PrintPrimeNum()
{
 char MASK;
 _asm mov MASK,10000000b
 for(unsigned int i=0;i<=PrimeNum;i++)
 {
  if((buffer[i/8]&MASK)==0)
  {
   printf("%d ",i);
  }
  _asm ror MASK,1
 }
}

void Prime::PrintPrimeNumFor_A2()
{
 for(unsigned int i=2;i<=PrimeNum;i++)
 {
  if(buffer[i]==0)
   printf("%d ",i);
 }
}

Prime::~Prime()
{

  delete[] buffer;
}

int main(int argc, char* argv[])
{
 Prime test(10000000);
 test.Calculate_A2();
 test.PrintPrimeNumFor_A2();
  
 

 return 0;
}