本文主要是介绍欧拉函数的求法（线性筛法？），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll phi[100001];
const int N=100000;
void init()
{
for ( int i=1;i<=N;i++)
phi[i]=i;
for ( int i=2;i<=N;i++)
{
if (i==phi[i])//判断i是不是质数（如果i不是质数那么在到达i之前phi[i]就会发生改变了）
for ( int j=i;j<=N;j+=i)
phi[j]=(phi[j])/i*(i-1);
}
}
int main()
{
int n;
init();
while (~ scanf ( "%d" ,&n))
{
printf ( "%d\n" ,phi[n]);
}
}
这篇关于欧拉函数的求法（线性筛法？）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
