蓝桥杯算法提高VIP-欧拉函数 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=2000010;
int prime[N],cnt=0;
int res[11],num[11],n,m,tmp;//m记录质数的个数 
bool p[N];
void FindPrime(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(p[i]==false)
		{
			prime[++cnt]=i;
			for(int j=i+i;j<=n;j+=i) p[j]=true;
		}
	}
}
int main(void)
{
	cin>>n;
	tmp=n;
	FindPrime(n);
	//cout<<"cnt="<<cnt<<endl;
	//for(int i=1;i<=cnt;i++) cout<<prime[i]<<" ";
	cnt=1;
	while(n!=1)
	{
		if(n%prime[cnt]==0) 
		{
			res[++m]=prime[cnt];
			while(n%prime[cnt]==0)
			{
				num[m]++;
				n/=prime[cnt];	
			} 
		}
		cnt++;
	}
	for(int i=1;i<=m;i++)
	{
		tmp/=res[i];
		tmp*=res[i]-1;
	}
	cout<<tmp<<endl;
	return 0;
}