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

2024-10-22 14:34:19

辗转相除法最大的用途就是用来求两个数的最大公约数。

用（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 ∴(11466,4284)=（4284，2898）
∵4284=2898×1+1386   ∴（4284，2898）=（2898，1386）
∵2898=1386×2+126   ∴（2898，1386）=（1386，126）
∵1386=126×11     ∴（1386，126）=126

所以（15750，27216）=126

辗转相除法比较适合用来求两个比较大的数的最大公约数。

代码如下：

#include<stdio.h>
int main()
{
  int a,b,temp,x;
  scanf("%d%d",&a,&b);
  if(a>b)
  {
    temp=b;
    b=a;
    a=temp;
  }
  while(b%a!=0)
  {
    x=b%a;
    b=a;
    a=x;
  }
  printf("%d",a);
}

以上所述是小编给大家介绍的C语言辗转相除法求2个数的最小公约数，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

C语言数据结构之连续存储数组的算法

数据结构之数组定义及基本操作数据结构中最基本的一个结构就是线性结构,而线性结构又分为连续存储结构和离散存储结构.所谓的连续存储结构其实就是数组. 数组本质其实也是数据的一种存储方式,既然有了数据的存储,就会涉及到如何对数据进行寻址的问题.首先,先说一下在数组中数据是如何存储的,在内存中,数组中的数据是以一组连续的数据集合的形式存在于内存中.当我们访问存在于内存中的数组时,我们应该找到其在内存中的地址,当我们找到数据的地址后我们就可以找到对应的数据.了解了以上知识后,我们就可以进行数组的设计了(
C语言行优先和列优先的问题深入分析

C语言行优先和列优先的问题深入分析摘要本文主要探讨的是"行优先"原则和"列优先"原则的问题. 1. 背景首先了解"行优先"和"列优先"的知识,这两种方式在数学上的直观描述如下,给定如下矩阵: 根据行优先的原则,其排序方式为根据列优先的原则,其排序方式为 2. 计算机领域的应用行列优先原则在计算机领域的应用主要如下.行优先或者列优先没有好坏,但其直接涉及到对内存中数据的最佳存储访问方式.因为在内存使用上,程序访问的内存
C语言 strftime 格式化显示日期时间的实现

C/C++程序中需要程序显示当前时间,可以使用标准函数strftime. 函数原型:size_t strftime (char* ptr, size_t maxsize, const char* format,const struct tm* timeptr ); 代码示例: #include <stdio.h> #include <time.h> int main () { time_t rawtime; struct tm * timeinfo; char buffer [12
详解C语言中的字符串拼接(堆与栈)

首先来看一个demo: int do_sth(int type) { char *errstr; switch(type) { case 1: errstr = "Error";break case 2: errstr = "Warn";break case 3: errstr = "Info";break case 4: errstr = "Debug";break default: return 0; } if (...)
C语言动态数组的使用实现代码

C语言动态数组从键盘读入n个整数,使用动态数组存储所读入的整数,并计算它们的和与平均值分别输出.要求尽可能使用函数实现程序代码.平均值为小数的只保留其整数部分. 样例输入: 5 3 4 0 0 2 样例输出: 9 1 样例输入: 7 3 2 7 5 2 9 1 样例输出: 29 4 代码如下: #include<stdio.h> int addAll(int a[],int N); int aveFun(int sum,int n); int main(){ int N; int sum
C语言中十六进制转十进制两种实现方法

C语言 · 十六进制转十进制问题描述从键盘输入一个不超过8位的正的十六进制数字符串,将它转换为正的十进制数后输出. 注:十六进制数中的10~15分别用大写的英文字母A.B.C.D.E.F表示. 样例输入 FFFF 样例输出 65535 思路:感觉自己的下面两个方法都对,但是···不说了[狡诈]... 方案一: #include<stdio.h> #include<math.h> #include<string.h> int main(){ char s[50]; s
深入探讨C语言中局部变量与全局变量在内存中的存放位置

C语言中局部变量和全局变量变量的存储类别(static,extern,auto,register) 1.局部变量和全局变量在讨论函数的形参变量时曾经提到,形参变量只在被调用期间才分配内存单元,调用结束立即释放.这一点表明形参变量只有在函数内才是有效的,离开该函数就不能再使用了.这种变量有效性的范围称变量的作用域.不仅对于形参变量,C语言中所有的量都有自己的作用域.变量说明的方式不同,其作用域也不同.C语言中的变量,按作用域范围可分为两种,即局部变量和全局变量.1.1局部变量局部变量也称为内部变量
C语言设计一个闪闪的圣诞树

控制台打印一个圣诞树:简简单单的C语言知识,真的很基础,小白也能看得懂哦 /******************************* 圣诞树 byC语言小白入门 *******************************/ #include<stdio.h> #include <stdlib.h> #include <time.h> #include<Windows.h> #define X 25 //画面长度 int background[20]
c语言全局变量和局部变量问题及解决汇总

1.局部变量能否和全局变量重名? 答:能,局部会屏蔽全局.要用全局变量,需要使用"::" 局部变量可以与全局变量同名,在函数内引用这个变量时,会用到同名的局部变量,而不会用到全局变量.对于有些编译器而言,在同一个函数内可以定义多个同名的局部变量,比如在两个循环体内都定义一个同名的局部变量,而那个局部变量的作用域就在那个循环体内. 2.如何引用一个已经定义过的全局变量? 答:extern 可以用引用头文件的方式,也可以用extern关键字,如果用引用头文件方式来引用某个在头文件中声明的全
C语言从txt文件中逐行读入数据存到数组中的实现方法

首先,要知道数据的存储格式是怎样的, 65 2 722 542 691 514 644 506 588 524 565 558 608 580 648 586 696 572 482 564 第一行表示数字的个数和维数,所以要先读入这些信息: <span style="white-space:pre"> </span>FILE *fp = fopen("2D_Jesscia_keypos.txt", "r"); if (
浅谈Linux C语言动态库及静态库

假设在math目录下已编辑好add.c sub.c div.c mul.c func_point.c文件,func_point.c为包含main()的源文件! 动态库的制作: 方法一: gcc -c -fPIC add.c sub.c div.c mul.c //-c表示生成.o目标文件,-f后加一些编译选项,PIC表示与位置无关 gcc -shared -o libmymath.so add.o sub.o mul.o div.o//创建共享库mymath,添加add.o,sub.o,mul.
C语言全局变量和局部变量详解及实例

C语言全局变量和局部变量详解核心内容: 1.局部变量和全局变量变量按照作用域分为:全局变量和局部变量全局变量的作用域:从定义位置开始到下面整个程序结束. 局部变量的作用域:在一个函数内部定义的变量只能在本函数内部进行使用. OK,上面的效果用Java语言实现一下: public class App1 { public static int k = 10;//相当于全局变量 public static void main(String[] args) { int i = 10;//局部变量

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

相关推荐

随机推荐