「bsoj3815」又一个素数 - 线性筛+乱搞

题目大意

求1~N 中素数的个数。

---

题目分析

线性筛肯定是要爆空间时间的，但是显然我们可以不筛$2$的倍数，然后将时间空间卡进限制。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num;
}
int Prime[6000005];
bool vst[50000005];
int n,cnt=0;
void Prime_Table(int n) {
	for(int i=3; i<=n; i+=2) {
		if(vst[(i-1)/2]==0)Prime[++cnt]=i;
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[(i*Prime[j]-1)/2]=1;
			if(i%Prime[j]==0)break;
		}
	}
}
int main() {
	n=Get_Int();
	if(n==1) {
		puts("0");
		return 0;
	}
	Prime_Table(n);
	printf("%d\n",cnt+1);
	return 0;
}