解题思路:
对于两个数互质的定义是两数的公约数只有1,我们也可以理解为他们的最大公约数是1
一说到最大公约数就不得不提欧几里得法了
欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。
计算公式gcd(a,b) = gcd(b,a mod b)。
它的时间复杂度是logn级别的
参考代码:
#include <stdio.h> int gcd(int a,int b){ if(a%b == 0) return b; gcd(b,a%b); } int main(){ int i,n; int count = 0; scanf("%d", &n); for(i = 1; i <= n-1; i++){ if(gcd(i,n) == 1) count++; } printf("%d", count); return 0; }
0.0分
156 人评分
C二级辅导-阶乘数列 (C语言代码)浏览:618 |
C语言程序设计教程(第三版)课后习题12.5 (C语言代码)浏览:830 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:522 |
简单的a+b (C语言代码)浏览:530 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:1258 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:549 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:529 |
数组与指针的问题浏览:718 |
用筛法求之N内的素数。 (C语言代码)浏览:533 |
模拟计算器 (C语言代码)浏览:2300 |