首页 > 其他 > 详细

欧拉函数

时间:2016-01-27 09:12:40      阅读:127      评论:0      收藏:0      [点我收藏+]
试题描述

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

输入
一个正整数n
输出
一个正整数表示f(n)的值
输入示例
8
输出示例
4
其他说明
输入的n在int范围内。
 
技术分享
 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 bool Euler(int a,int n)   //Euler就是欧拉的意思 
 6 {
 7     int i;
 8     if(n%2==0 && a%2==0) return 0; //因为下面的循环当 i==1 || i==2 时不执行 
 9     for(i=2;i<a;i++)
10     {
11         if(a%i==0 && n%i==0) return 0;   //判断是否互质 
12     }
13     //printf("%d\n",a);
14     return 1;
15 }
16 int main()
17 {
18     int n;
19     scanf("%d",&n);
20     int ans=0;
21     for(int i=1;i<n;i++)
22     {
23         if(Euler(i,n)) ans++;   //如果互质ans++ 
24     }
25     printf("%d",ans);
26     //system("pause");
27     return 0;
28 }
欧拉函数

欧拉函数

原文:http://www.cnblogs.com/YXY-1211/p/5162086.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!