时间复杂度约为 $O(n\ \frac{n}{\ln n})$

#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
map<int,int> cnt;
bool flag = 1;
const int N=1e9;
int main(){
	auto start = clock();
	prime.push_back(2);
	cnt[2]=0;
	for(int i=3;i<=N;i++){
		flag = 1;
		for(int j:prime){
			cnt[j] = (cnt[j] + 1) % j;
			flag = flag & (cnt[j]!=0);	
			//printf("%d:cnt[%d]=%d\n",i,j,cnt[j]);
		}
		if(flag){
			prime.push_back(i);
			cnt[i] = 0;
			if(prime.size()%500==0) printf("find prime:%d cnt:%d sqrt:%d ln:%d use:%d\n", i,prime.size(),(int)sqrt(i),i/(int)log(i),double(clock()-start)/CLOCK_PRE);
		}
	}
	return 0;
}