c++一道题：求1-n中与n互质的数，输入n,输出一行一个数值

更新时间：2019-02-01 23:30:04 175次访问

求1-n中与n互质的数，输入n,输出一行一个数值

样例输入：

29

输出：

6

用c语言编了一个，仅供参考，源代码如下：

#include<stdio.h>

int gcd(int a,int b)                         //该函数求a,b两数的最大公因数

{

     int t;

     while (b != 0)                          //使用“辗转相除法”求解最大公因数

     {

          t = b;

          b = a % b;

          a = t;

     }

     return a;                                   //返回a,b两数的最大公因数

}

int main()

{

     int i;                                         //循环变量

     int n;                                        //n，输入参数

     int gcd_ab;                              //最大公因数

     int number=0;                         //互质数计数

     printf("Please INPUT A Positive Number:  ");

     scanf("%d",&n);                       //输入n

     for(i=1; i<n; i++)                    //从1开始到n-1循环，依次判断i和n是否互质（n必然与n不互质）

     {

          gcd_ab = gcd(n, i);             //计算i和n的最大公因数

          if (gcd_ab == 1)                 //如果两个数a,b的最大公因数为1，两数互质

               number++;                   //如果i和n互质，计数加1

     }

//输出结果

     printf("From 1 to %d, There are(is) %d numbers which is coprime with %d.",n, number, n);

     return 0;

}

输出结果如下：