给定一个整数 nn,请问有多少个整数 i满足条件:gcd(i, n) = 1,1<=i<=n;
输入一行,输入一个整数 n(n<=10^9)。
输出一行,输出一个整数,表示符合条件的整数个数。
16
8
#include<iostream>
#define MAX 1000000000
using namespace std;
int gcd(int a,int b)
{
return b==0 ?a:gcd(b,a%b);
}
int main()
{
int n,count=0;
cin>>n;
for(int i=1;i<n;++i)
{
if(gcd(i,n)==1)
{
count++;
}
}
cout<<count;
return 0;
}
#include<iostream>
#include<vector>
#define MAX 1000000000
using namespace std;
bool map[MAX];
void prime(int n)
{
map[0]=map[1]=1;
for(int i=2;i*i<n;++i)
{
if(!map[i])
{
for(int j=i*i;j<n;j+=i)
{
map[j]=1;
}
}
}
}
int gcd(int a,int b)
{
return b==0 ?a:gcd(b,a%b);
}
int main()
{
int n;
cin>>n;
prime(n);
float count=(float)n;
for(int i=1;i<n;++i)
{
if(!map[i]&&(n%i==0))
{
count*=(1-1/(float)i);
}
}
printf("%.0f",count);
return 0;
}
主要的还是在套公式,其中的while循环是亮点
#include <iostream>
using namespace std;
int euler(int n)
{
int res=n;
for(int i=2;i*i<=n;i++)
{
//因为是在遍历因子,所以找一半就行了
if(n%i==0)
{
//cout<<"因子 = "<< i<<" 此时n = ";
//如果i是n的第一个因子即最小那个
res=res/i*(i-1);
//公式变形:
//∮(n) = n*(1-P1)/P1*……*(1-Pn)/Pn
//cout<<n<<endl;
while(n%i==0)
{
//寻找下一个质因子
n/=i;
//cout<<"while 中 = "<<n<<endl;
}
// cout<<"出while后 = "<<n<<endl;
}
}
if(n>1)
{
//大于sqrt(n)的质因子会导致循环提前结束,如42 = 2*3*7
res=res/n*(n-1);
}
return res;
}
int main()
{
int n;
cin>>n;
cout<<euler(n);
//euler(30);
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁