首页 > 其他分享 >欧几里得(辗转相除法)求两个数最大公约数

欧几里得(辗转相除法)求两个数最大公约数

时间:2022-11-09 23:44:37浏览次数:50  
标签:return int 欧几里得 EA 最大公约数 除法 remainder


#include<stdio.h>
int  EA(int a,int  b) // 欧几里得算法
{
    int  remainder;
    int  middle;
    if (a < b) // a,b交换值
    {
        b = a + b;
        a = b - a;
        b -= a;
    }else if(a==b)
    {
        return a;
    }
    do 
    {
        remainder = a % b;
        if (remainder == 0)return b;
        a = b;
        b = remainder;

    } while (remainder!=0);
    return b;
}
int main() 
{
    int a, b;
    scanf("%d%d",&a ,&b);
    int c = EA(a,b);
    printf("%d",c);
    return 0;
}



image

标签:return,int,欧几里得,EA,最大公约数,除法,remainder
From: https://www.cnblogs.com/JK8395/p/16875598.html

相关文章

  • 扩展欧几里得算法
    题目:#include<bits/stdc++.h>usingnamespacestd;intexgcd(inta,intb,int&x,int&y){if(b==0){x=1,y=0;returna;}intx1,y1......
  • 基础循环:短除法—“倒”数
    题目描述:输入一个正整数N(0<N<2147483647),将这个数倒着合成一个新数后输出。比如:543,倒过来是345(请注意:34500,倒过来是543,不是00543)!思路解析:引入两个变量n,t(注意t要定......
  • 计算机运算方法————除法
    原码除法符号位单独计算操作数的绝对值的原码以及绝对值的补码参与运算运算的次数位参与运算的被除数的尾数的个数n次(1)恢复余数法(2)不恢复余数法(加减交替......
  • 最大公约数最小公倍数的探索(三种方法)
    本题要求两个给定正整数的最大公约数和最小公倍数。第一遍自己做时,根据原理暴力求解    结果可想而知超时了 看完翁恺老师的视频,学会第二种方法———辗转相......
  • 【poj1061】青蛙的约会(扩展欧几里得)
    不妨设青蛙A的出发点坐标是\(m1\),青蛙B的出发点坐标是\(n1\)。青蛙A一次能跳\(m\)米,青蛙B一次能跳\(n\)米,跳一圈长\(l\)米,设青蛙A、B跳了\(x\)次。那么题目要求的是满足下......
  • c语言求最大公约数(c语言求最大公约数和最小公倍数代码)
    C语言中求两个数的最大公约数的公式是什么?inti,a=3,b=6;intmax=b;//初始化b大,下面判断如果a>b就把a给max//判断a,b大小if(a>b)max=a;for(i=max;i>0;i--)//公约数肯定不......
  • 试除法
    #define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ inti=0;  for(i=100;i<=200;i++) { ints=0; for(s=2;s<i;s++) {......
  • C语言求输入两个数最大公约数和正负号变化的分数之和
    一.求两个数最大公约数问题描述输入两个数,输出这两个数的最大公约数解题思路辗转相除法;它的具体做法是:用较大数除较小数,再用除数去除出现的余数(第一余数),再用第一余数去除出......
  • 最大公约数,最小公倍数
    #include<stdio.h>intmain(){ inta=6; intb=12; intr; intsum=a*b; r=a%b; while(r!=0){ a=b; b=r; r=a%b; } printf("最......
  • BigDecimal的加减乘除(包含除法保留两位小数,并不要四舍五入)
    同于经常要用到BigDecimal作数据运算,这里记录一下,总是忘记写法,懒得每次用再去百度了 BigDecimal的加法:BigDecimala=newBigDecimal("1");BigDecimalb=newBigD......