线性求欧拉函数

#include<cstdio>
using namespace std;
int n,prime[1000001],tot,phi[1000001];
bool mark[1000001];
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		if(!mark[i])prime[++tot]=i,phi[i]=i-1;
		for(int j=1;j<=tot;j++){
			if(i*prime[j]>n)break;
			mark[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
}