|
#include<iostream>
#include<bitset>//但是它是没有要求的,这是对空间要求比较高的情况下用的位操作
#include<time.h>//它的使用是在用了using namespace std后,还要加上.h,同样的对于stdlib.h,math.h也是如此
#include<stdlib.h>
#include<math.h>
#define N 100000000
using namespace std;
int sieveSTL()
{
//cout<<"请输入要查找的范围如:1~x"<<endl;
//unsigned int n;
//cin>>n;
bitset<N>& p=*new bitset<N>;//没有实现动态的输入吗?
p.set();//将所有的位都置于1;
int num=N-2;//1,0根本没有判断到
int r=sqrt(N);
for(int i=2;i<=r;i++)//1,0根本没有判断到,看起点就知道
if(p.test(i))//取第i位的值是0还是1
for(int j=i*i;j<p.size();j+=i)//这里j+=i即j=i*(i+1);
if(p.test(j) && num--) p.reset(j);//与set的含义相反,同这句(p[j/32] &(1<<j%32) && num--)相同\
delete[] &p;//这样子写就必须是地址常量
return num;
}
int sieve()
{
cout<<"请输入要查找的范围如:1~x(这个范围不包括x,请注意)"<<endl;
int n;
cin>>n;
int t=n/8;
unsigned int* p;
if(!(n%8))
{if(n<8)
t=4;
else p=(unsigned int*) malloc(t);
}
else
{ t++;p=(unsigned int*) malloc(t);}
memset(p,255,t);//将t个字节初始化为全1,这里只能对字节操作(是它的单位)
int num=n-2;//这里要知道,我们对num的操作,是根据这个位是不是非素数,但有一个数据是判断不到的,就是1,它是从2开始的
int f=sqrt(n);
for(int i=2;i<=f;i++)
if(p[i/32] & (1<<i%32))//1左移i%32位,这里有为什么要左移的问题,因为我们这个p相当于多个整型数据末是0,并不是起点因为这里用的是取余的操作
//它既兼顾了1这个数的作用,同时又有了一个移位的操作
//这个操作还有一重意思,就是如果说这个判断是假的,那么意味着,它的所有的倍数都置0了,它可能是由于它的因子将它置的原因
for(int j=i*i;j<n;j+=i)//如果说有一个数n,它有因子,那么我们对它开方得其根,那么它的因子一定会小于这个算术根,即因子的平方会小于n
if(p[j/32] &(1<<j%32) && num--)//位操作要高于逻辑操作,这句话的含义是,p[j/32] &(1<<j%32)是1,而本身j这个元素不是素数,要去掉的,这个结果是1
//表示这个非素数,以前并没有发现,如果是0,表示以前发现了,那么那时的num就已经自减了,如今不用再减了.
p[j/32] &=~(1<<j%32);//那么当这个取i是这个因子的值时,就不会漏了对这个n的判断了
free(p);
return num;
}
int main()
{
clock_t start=clock();
cout<<sieve();
cout<<" "<<(clock()-start)/CLK_TCK<<endl;
return 0;
}
//这里有一人些编程的技巧就是:对素数的判断操作和一个统计的操作问题,如果我们将两个分开操作的话,那么又要多循环一遍,还不如边判断时就统计它
//这里恰好用了一个倒减的方式,刚好符合了,我们对素数的判断恰好看它是不是非素数,统一起来了.
//若是int num=n-1;这里要知道,我们对num的操作,是根据这个位是不是非素数,但有一个数据是判断不到的,就是1,它是从2开始的,而此时,我们说这个n的最后值是不可能达到的
//这里的内存分配是这样的,我们的位是从0~n/32-1,这对我们的最后的条件判断是j<n,还是j<=n有影响,因为p[j/32]是不存在的,写成j<=n;则最后会超出申请的空间的范围
|
