admin 管理员组文章数量: 887021
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;
}
版权声明：本文标题：C++ ,C 筛法求素数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686605069h16105.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论