int n;//求1 ~ n之间的素数
int prime[N],cnt;//prime数组存放素数 cnt为prime的长度
int st[N];//数字i是否为素数


void euler(){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&prime[j]<=n/i;j++){
			st[i*prime[j]]=1;
			if(i%prime[j]) break;
		}
	}
	return ;
}