C语言最大公约数示例教程

目录
  • 穷举法
  •  辗转相除法
  •  辗转相减法

穷举法

（1） i= a ，b中较小的数
（2）若a，b能同时被i整除，则i即为最大公约数，结束
（3）若不能，则 i--，再回去执行（2）

#include<stdio.h>
int main()
{
	int i = 0;
	int j = 0;
	scanf("%d %d", &i, &j);
	int k = i > j ? i : j;//i>j,k=i;i<j,k=j
	while(1)
	{
		if (i%k == 0 && j%k == 0)
		{
			printf("最大公约数为；%d\n", k);
			break;
		}
		k--;
	}
	return 0;
}

 辗转相除法

辗转相除法求两个数的最大公约数的步骤如下：
（1）先用小的一个数除大的一个数，得第一个余数；
（2）再用第一个余数除小的一个数，得第二个余数；
（3）又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数。

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &a, &b);
	while (c = a%b)
	{
		a = b;
		b = c;
	}
	printf("%d\n", b);
	return 0;
}

 辗转相减法

两整数a和b：
（1） 若a>b，则a=a-b
（2）若a<b，则b=b-a
（3） 若a=b，则a（或b）即为两数的最大公约数，结束
（4）若a≠b，则再回去执行（1）

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d%d", &a, &b);
	int ret = 0;
	while (1)
	{
		if (a < b)
		{
			int tmp = 0;
			tmp = a;
			a = b;
			b = tmp;
		}
		ret = a - b;
		if (ret == b)//判断
		{
			printf("ret = %d", ret);
			break;
		}
		else//交换
		{
			a = b;
			b = ret;
		}
	}
	return 0;
}

以上就是C语言最大公约数示例详解的详细内容，更多关于C语言最大公约数的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言辗转相除法求2个数的最小公约数

    辗转相除法最大的用途就是用来求两个数的最大公约数. 用(a,b)来表示a和b的最大公约数. 有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c). (证明过程请参考其它资料) 例:求 15750 与27216的最大公约数. 解: ∵27216=15750×1+11466 ∴(15750,27216)=(15750,11466) ∵15750=11466×1+4284  ∴(15750,11466)=(11466,4284) ∵11466=4284×2+2898  ∴(114

  • 详解C语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0).根据通式写出算法不难,这里就不给出了.这里给出<编程之美>上的算法,主要是为了减少迭代的次数.      对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1).另外,如果x = p * x1,假设p为素数

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

  • C语言循环结构详解

    C语言循环结构详解

    目录 break语句 continue语句 C语言循环结构 一.goto 语句(现在一般很少用) 1.语句介绍: 2.语法结构: 3.goto 语句程序示例: 二.do-while语句 1.语句介绍: 2.语法结构: 3.do-while 流程图: 4.do-while 语句程序示例: 三.while 语句 1.语句介绍: 2.语法结构: 3.while 循环流程图: 4.while 语句程序示例: 四.for 循环语句: 1.语句介绍: 2.语法结构: 3.for 循环语句流程图 4.for

  • C语言程序设计第五版谭浩强课后答案(第二章答案)

    C语言程序设计第五版谭浩强课后答案(第二章答案)

    1. 什么是算法?试从日常生活中找3个例子,描述它们的算法 算法:简而言之就是求解问题的步骤,对特定问题求解步骤的一种描述. 比如生活中的例子: 考大学 首先填报志愿表.交报名费.拿到准考证.按时参加考试.收到录取通知书.按照日期到指定学校报到. 去北京听演唱会 首先在网上购票.然后按时坐车到北京,坐车到演唱会会场. 把大象放进冰箱 先打开冰箱门,然后将大象放进冰箱,关冰箱. 2. 什么叫结构化的算法?为什么要提倡结构化的算法? 结构化算法:由一些顺序.选择.循环等基本结构按照顺序组成,流程的转

  • C语言最大公约数示例教程

    目录 穷举法  辗转相除法  辗转相减法 穷举法 (1) i= a ,b中较小的数 (2)若a,b能同时被i整除,则i即为最大公约数,结束 (3)若不能,则 i--,再回去执行(2) #include<stdio.h> int main() { int i = 0; int j = 0; scanf("%d %d", &i, &j); int k = i > j ? i : j;//i>j,k=i;i<j,k=j while(1) { if

  • Golang语言学习拿捏Go反射示例教程

    Golang语言学习拿捏Go反射示例教程

    目录 1. 反射简介 1.1 反射是什么? 1.2 为什么需要反射? 2. reflect包 2.1 基本反射 2.2 反射与指针 2.3 反射与对象 2.4 反射与函数 2.5 反射例子 3. 总结 1. 反射简介 1.1 反射是什么? Go语言提供了一种机制在运行时更新和检查变量的值.调用变量的方法和变量支持的内在操作,但是在编译时并不知道这些变量的具体类型,这种机制被称为反射.反射也可以让我们将类型本身作为第一类的值类型处理. 反射是指在程序运行期对程序本身进行访问和修改的能力,程序在编译

  • C语言共用体union作用使用示例教程

    C语言共用体union作用使用示例教程

    目录 共用体 union 开锅解构 小结一手 共用体 union 什么是共用体 union?这个共用体,估计大家平时在代码也比较少见,我去看了;其实这个共用体 union(也叫联合体)跟结构体定义是非常像的,比如说:类型定义.变量定义.使用方法上很相似.就像下面两个例子一样,把许多类型联合在一起 union st{ char a; int b; } 共用体也是一种自定义类型,可以通过它来创建变量,例如: union num{ int n; char ch; double f; }; union

  • Go语言快速入门指针Map使用示例教程

    目录 1. 指针 1.1 指针地址和指针类型 1.2 指针取值 1.3 空指针 1.4 new 的使用 1.5 new与make的区别 2. Map 2.1 什么是Map key,value存储 hash冲突 hash冲突的常见解决方法 开放定址(线性探测)和拉链的优缺点 2.2 Map 定义 2.3 map基本使用 2.4 map的遍历 2.5 map判断某个键是否存在 2.6 map使用delete()函数删除键值对 1. 指针 区别于C/C++中的指针,Go语言中的指针不能进行偏移和运算,

  • 详解Java 10 var关键字和示例教程

    关键要点 Java 10引入了一个闪亮的新功能:局部变量类型推断.对于局部变量,现在可以使用特殊的保留类型名称"var"代替实际类型. 提供这个特性是为了增强Java语言,并将类型推断扩展到局部变量的声明上.这样可以减少板代码,同时仍然保留Java的编译时类型检查. 由于编译器需要通过检查赋值等式右侧(RHS)来推断var的实际类型,因此在某些情况下,这个特性具有局限性,例如在初始化Array和Stream的时候. 如何使用新的"var"来减少样板代码. 在本文中,

  • 超详细的c语言字符串操作函数教程

    超详细的c语言字符串操作函数教程

    目录 一,常量指针与指针常量 二,字符串长度问题 三,c语言中的字符串拷贝函数 1) strcpy() 2), strncpy() 3), strcat() 4), strncat() 5), strcmp() 6), strncmp() 7), sprintf() 8) sscanf() 9) strchr() 10), strstr() 11) strtok() 总结 我们知道,c/c++之所以使用起来灵活,很大原因归因于它能够它对能够对内存的直接操作,所以本文我主要讲述一下c中的字符串操作

  • Java程序中Doc文档注释示例教程

    Java程序中Doc文档注释示例教程

    目录 Doc注释规范 @符号的用处 如何生成Doc文档 第一个:Dos命令生成 第二个:IDE工具生成 许多人写代码时总不喜欢写注释,每个程序员如此,嘿嘿,我也一样 不过,话说回来,该写还是要写哦!没人会喜欢一个不写注释的程序员,当然,也没有一个喜欢写注释的程序员,今天,我们就来说说Java注释之一--Doc注释 我们知道,Java支持 3 种注释,分别是单行注释.多行注释和文档注释,我们来看看他们的样子 //单行注释   /* 多行注释 */   /** *@... *.... *文档注释 *

  • Go语言七篇入门教程六网络编程

    目录 1. Socket 编程 1.1 Dial()函数 2. HTTP 编程 2.1 HTTP 客户端 2.2 HTTP 服务端 2.2.1 处理 HTTP 请求 3. RPC 编程 3.1 Go 语言中的 RPC 支持与处理 3.2 Gob 简介 3.3 设计优雅的 RPC 接口 1. Socket 编程 在 Go 语言中编写网络程序时,我们将看不到传统的编码形式.以前我们使用 Socket 编程时,会按照如下步骤展开. 建立 Socket:使用 socket()函数. 绑定 Socket:

  • javascript数据类型基础示例教程

    javascript数据类型基础示例教程

    js中的输入输出语句 方法 说明 归属 alert(msg) 浏览器弹出警示框 浏览器 console.log(msg) 浏览器控制台打印输出信息 浏览器 prompt(info) 浏览器弹出输入框,用户可以输入 浏览器 注:prompt(info)获取的输入都是字符串类型,跟python中的input()类似. <script> prompt("请输入:"); alert('你好呀!小可爱!'); console.log('阿牛最帅啦!'); </script>

  • Kotlin函数使用示例教程

    Kotlin函数使用示例教程

    目录 我们先看看简单的函数 我们写一个求和函数 函数头 函数体 调用函数非常简单 反编译Java源代码步骤 接下来我们来看看匿名函数 这是接口的声明 我们先看看简单的函数 // 前面的文章我们了解到它是入口函数 fun main() { } // 对应的Java 语言,熟悉的Java 的朋友会发现,哈哈,这就是一个Java静态方法 // 我们通过两种语言的对比,能够对函数有一个更好的理解 public static final void main() { } // 如果没有 Java 基础,不适

随机推荐