1 popcount()

  int popcount(int x){
	int ans=0;
	while(x){
		ans+=x&1;
		x>>=1;
	}
	return ans;
}

2 gcd()

int gcd(int x,int y){
	if(y==0)return x;
	return(y,x%y);
}

3 欧式质数筛

  void oushai(int n){
    bool vis[1000010];
    vector<int> ans;
	for(int i=1;i<=n;i++){
		vis[i]=1;
	}
	vis[0]=vis[1]=0;
	for(int i=2;i<=n;i++){
		if(vis[i]!=0){
			ans.push_back(i);
		}
		for(int j=0;j<ans.size();j++){
			if(ans[j]*i>n)break;
			vis[ans[j]*i]=0;
			if(ans[j]*ans[j]>n)break;
		}
	}
}