在期末被各科的大作业碾压快要窒息之际，百忙之中抽空上牛客网逛了逛，无意中发现一道好题，NowCoder猜想，题意很明显，就是个简单的素数筛法，但竟然超内存了，我晕(+﹏+)~ 明明有 3 万多 k 的空间限制……于是我不打表，试了试最暴力的做法，赤裸裸的做法果然超时了，无奈，只好对素数筛法进行位压缩了，这是我目前所能想到的方法了，第一次用上这样的特技，还是调了好一会（位数组里不能用 bool 来定义，具体的话好像 bool 和 int 之类的整型稍有不同；也不能用 int，因其最高位是正负标志位，所以只好用 unsigned int了，同样的原理，用 unsigned char, unsigned short, unsigned long long 等无符号整型都可以），贴个代码先，注释的为纯暴力：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf = 0x3fffffff;
const int N = 1e7; class bitarray {
unsigned int sign[];
public:
bitarray() { memset(sign,,sizeof(sign)); }
bool rid(const int &x) const {
return sign[x / ] & ( << (x % ));
}
void wid(const int &x, const int &v) {
sign[x / ] |= (v ? ( << (x % )) : );
}
}; int pri[];
int init_pri(int n = N) {
bitarray bit;
int c = ;
for(int i = ; i <= n; ++i)
if(!bit.rid(i)) {
pri[c++] = i;
for(int j = i << ; j <= n; j += i) bit.wid(j,);
}
return c;
} /*
inline bool isprime(const int &x) {
if(x == 1) return 0;
int m = sqrt(x +0.5);
for(int i = 2; i <= m; ++i)
if(x % i == 0) return 0;
return 1;
} inline int num(const int &n) {
int res = 0;
for(int i = 1; i <= n; i += 2)
if(isprime(i)) ++res;
return n >= 2 ? res + 1 : res;
}
*/ int main() {
int n,num = init_pri();
pri[num++] = inf;
while(~scanf("%d",&n),n) {
int id = lower_bound(pri, pri+num, n) - pri;
if(pri[id] == n) printf("%d\n",id + );
else printf("%d\n",id);
}
return ;
}
提交后发现无论是哪种做法，后台的内存计算都和我自己手算的差很远，不知它是怎么计算的。。。