桐桑入梦


私信TA

用户名:wanggongsheng

访问量:85619

签 名:

坚定拥护在以习总书记为核心的党中央周围。

等  级
排  名 6
经  验 15603
参赛次数 3
文章发表 163
年  龄 20
在职情况 学生
学  校
专  业

  自我简介:

解题思路:

注意事项:

参考代码:

#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;
}


 

0.0分

0 人评分

  评论区