对埃氏筛加了一个小优化（用质数 $p$ 去筛掉合数时从 $p\times p$ 开始筛），也能通过此题：

int pme[N],ok[N],top;
void shai(int n){
	fo(i,2,n) if(!ok[i]){
		pme[++top]=i;
		fo(j,i,n/i) ok[i*j]=1;
	}
	//fo(i,1,top) printf("%d ",pme[i]);puts(""); 
}

请问这样写的复杂度是多少？谢谢巨佬们！