求素数个数筛法版.cpp

求素数

//算法一
#include<iostream>
#include<bitset>
#include<time.h>
using namespace std;
/*
int main(){
	clock_t start, finish;
	start = clock();
	bitset<100000000> *p = new bitset<100000000>;
	p->set();
	for(int i=2;i<=10000;i++){
		if(p->test(i)){
			for(int j=i*i;j<p->size();j+=i){
				p->reset(j);
			}
		}
	}
	int num=0;
	for(i=2;i<100000000;i++){
		if(p->test(i)){
			num++;
		}
	}
	cout<<num<<endl;
	delete[] p;
	finish = clock();
	cout<<((finish-start)/CLOCKS_PER_SEC);
}
*/
/*
//算法二
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<memory.h>
#include<iostream.h>

int count(unsigned int a){
	int sum=0;
	for(unsigned int x=a; x; x>>=1){
		if(x & 1){
			sum++;
		}
	}
	return sum;
}

void sieve(unsigned int *p){
	for(int i=2; i<=10000; ++i){
		if(i==50){
			for(int t=1;t<=32;t++){
				int q = p[1]%2;
				p[1]=p[1]/2;
				cout<<q;
			}
			cout<<endl;
			
		}
		if(p[i/32] & (1<<i%32)){
			for(int j=i*i;j<100000000;j+=i){
				p[j/32] &= ~(1<<j%32);
			}
		}
	}
}

int main(){
	clock_t start,finish;
	start =clock();
	unsigned int *p = (unsigned int *)malloc(12500000);
	if(!p){
		printf("no enough memory.\n");
		return 1;
	}
	memset(p,255,12500000);
	sieve(p);
	int num =-2;
	for(int i=0;i<12500000/4;i++){
		num+=count(p[i]);
	}
	free(p);
	finish=clock();
	double time=(double)((finish-start)/CLOCKS_PER_SEC);
	printf("%d,%7.3f",num,time);
}
*/
main(){
	clock_t start1, start2, finish1, finish2;
	start1 = clock();
	long int  i, j;
	for(i = 0; i<1000000000; i++){
		j = 1000000000 / 1024;
	}
	finish1 = clock();
	start2 = clock();
	for(i = 0; i<1000000000; i++){
		j = 1000000000 >> 10;
	}
	finish2 = clock();
	double time1 =(double)((finish1 - start1) / CLOCKS_PER_SEC);
	double time2 =(double)((finish2 - start2) / CLOCKS_PER_SEC);
	printf("%7.6f\n%7.6f",time1,time2);
}