欧拉函数

试题描述

我们都知道欧拉函数f(n)表示的意思是：小于或等于n的正整数中与n互质的数的数目。例如f(8)=4，因为1,3,5,7均和8互质。给定一个正整数n，输出f(n)的值。

输入

一个正整数n

输出

一个正整数表示f(n)的值

输入示例

8

输出示例

4

其他说明

输入的n在int范围内。

#include <iostream>

using namespace std;

bool Euler(int a,int n)   //Euler就是欧拉的意思 
{
    int i;
    if(n%2==0 && a%2==0) return 0; //因为下面的循环当 i==1 || i==2 时不执行 
    for(i=2;i<a;i++)
    {
        if(a%i==0 && n%i==0) return 0;   //判断是否互质 
    }
    //printf("%d
",a);
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<n;i++)
    {
        if(Euler(i,n)) ans++;   //如果互质ans++ 
    }
    printf("%d",ans);
    //system("pause");
    return 0;
}