G09 筛法求欧拉函数

#include<bits/stdc++.h>
using namespace std;
const int N=2e7;
int prime[N],pr,phi[N+10];
bool v[N+10];
void init()
{
	pr=0;phi[1]=1;
	memset(v,0,sizeof(v));
	for(int i=2;i<=N;i++)
	{
		if(v[i]==0)prime[++pr]=i,phi[i]=i-1;
		for(int j=1;(j<=pr)&&(i*prime[j]<=N);j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else 
			{
				phi[i*prime[j]]=phi[i]*(prime[j]-1); 
			}
		}
	}
} 
int main()
{
	init();
	int n;scanf("%d",&n);
	while(n--)
	{
		int x;scanf("%d",&x);
		printf("%d\n",phi[x]);
	}
	return 0;
}

G09 筛法求欧拉函数

#include<bits/stdc++.h>
using namespace std;
const int N=2e7;
int prime[N],pr,phi[N+10];
bool v[N+10];
void init()
{
	pr=0;phi[1]=1;
	memset(v,0,sizeof(v));
	for(int i=2;i<=N;i++)
	{
		if(v[i]==0)prime[++pr]=i,phi[i]=i-1;
		for(int j=1;(j<=pr)&&(i*prime[j]<=N);j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else 
			{
				phi[i*prime[j]]=phi[i]*(prime[j]-1); 
			}
		}
	}
} 
int main()
{
	init();
	int n;scanf("%d",&n);
	while(n--)
	{
		int x;scanf("%d",&x);
		printf("%d\n",phi[x]);
	}
	return 0;
}