今天遇到一道奇怪的程序题，和平常的不同。同样都是互质，但是一般的题目都是判断两个数字是否互质，但这道题则是给定一个数字n，要求输出所有小于等于n的与n互质的数，题目已经在下面给出：
质数与互质概念不是同一个，质数指的是一个数仅有1和它自己本身可以被整除；而互质则指的是两个数只有1是共同的因数，有些人可能会将两者混为一谈。本篇文章是以互质为主题，接下来以互质作为主要内容，不过不得不说，这两者的核心都是一样的，采取欧几里得算法（又叫辗转相除法），通常用gcd表示，欧几里得算法应用范围非常广泛，在今后的blog中我会专门写一篇文章来讲欧几里得算法。
言归正传，这道题有多行测试数据，因此我们可以用while语句作为循环，考虑到会超时，于是我打算用自定义函数：
被除数a和除数b相除取余数c，将余数c给除数b，除数b给被除数a，以此往复，直到直到b为0，作为结束的标志。
本题考察的是自定义函数，其中欧几里得算法非常重要。
以下是完整代码：
1 #include <stdio.h> 2 int Gcd(int m,int n) 3 { 4 int o; 5 while(n>0) 6 { 7 o=m%n; 8 m=n; 9 n=o; 10 } 11 return m; 12 } 13 int main() 14 { 15 int a,i,b,s; 16 while(scanf("%d",&a)!=EOF) 17 { 18 if(a==1) 19 { 20 printf("1\n"); 21 } 22 else{ 23 s=0; 24 for(i=1;i<a;i++) 25 { 26 b=Gcd(i,a); 27 if(b==1) 28 { 29 s++; 30 } 31 } 32 printf("%d\n",s); 33 } 34 } 35 return 0; 36 }
原文：https://www.cnblogs.com/jackwang-sparrow/p/11874271.html