欧拉筛（线性筛）7.1@亿万星辰

/*根据三条性质推导即可。
线性筛中每一个数字最多只会被筛一次，因此正好可以对每一个数字求欧拉函数。
线性筛正好是由小的数字筛到大的数字 or 正好是指数
前者用后两条性质 后者用第一条性质即可。
三条性质如下：
 1.如果n为某一素数的幂次，那么: φ(p^a)=(p-1)*p^(a-1)  (φ(p)=p-1) 
 2.如果i mod p=0,那么φ(i*p)=p*φ(i)
 3.如果i mod p≠0，那么φ(i*p)=φ(i)*(p-1)*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000000
bool f[MAXN+10];
int phi[MAXN+10],pri[MAXN+10],cnt; 
void Get_phi(int n)//欧拉筛 
{
	int i,j;
	phi[1]=1;
	for(i=2;i<=n;i++){//循环赋值 
		if(!(f[i])){//判断是否为素数 
			pri[++cnt]=i;//保存新筛素数 
			phi[i]=i-1;//欧拉筛性质1
		}
		for(j=1;j<=cnt&&i*pri[j]<=n;j++){
			f[i*pri[j]]=1;
			if(i%pri[j]==0) {//判断是否为i是否为已知素数的倍数 
				phi[i*pri[j]]=phi[i]*pri[j];//欧拉筛性质2
				break;
			}
			else phi[i*pri[j]]=phi[i]*(pri[j]-1);//欧拉筛性质3
		}
	}
 } 
 int main()
 {
 	int n;
 	scanf("%d",&n);
 	Get_phi(n);
 	printf("cnt:%d\n",cnt);
 	for(;n;n--)
 	{
 		printf("%d %d\n",n,phi[n]);
	 }
	 return 0;
 }