`

基本算法之3---最大公约数

阅读更多

简要概述:

根据递推策略设计辗转相除法:a,b的最大公约数,也是a%b的约数。以此方法递推,直到余数为0

 

代码实现:

import java.util.Scanner;

public class Test{
	//最大公约数
  public static int yue(int n,int m){ 
	  if(n==0||m==0)
		  return 0;
	  if(n<m){
		  int temp = n;
		  n = m;
		  m = temp;
	  }
	  int r = n%m;
	  while(r!=0){
		  n=m;
		  m=r;
		  r=n%m;
	  }
	  return m;
  }
  
  //最小公倍数
  public static int bei(int n,int m){
	  if(yue(n,m)==0)
		  return 0;
	  return n*m/yue(n,m);
  }
  

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		System.out.println("最大公约数:"+yue(n,m));
		System.out.println("最小公倍数:"+bei(n,m));

	}
}
/**基本思想:
 *  辗转相除法(也可以用相减法,本质相同)
 */

 

分享到:
评论

相关推荐

    欧几里德算法求最大公约数——C++代码

    欧几里得算法,也称为辗转相除法,是计算两个正整数最大公约数(Greatest Common Divisor, GCD)的一种经典方法。该算法基于以下原理:两个正整数a和b(a&gt;b)的最大公约数等于a除以b的余数c和b之间的最大公约数。...

    求最大公约数最小公倍数的3种算法的流程图

    辗转相除法,又称欧几里得算法,是最古老的求解最大公约数的方法之一。其基本思想是:对于任意两个正整数a和b(a&gt;b),它们的最大公约数等于a除以b的余数c与b之间的最大公约数。可以表示为GCD(a, b) = GCD(b, a % b)...

    设计出3个版本的求最大公约数的算法

    总结,求最大公约数的算法有多种实现,如欧几里得算法、质因数分解法和更相减损术,它们各有优缺点。理解并实现这些算法,可以深化对数论和算法设计的理解,同时对优化程序性能具有重要意义。在实际应用中,应根据...

    最大公约数算法(很好哦)

    它的基本思想是:对于任意两个正整数a和b(a&gt;b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。即GCD(a, b) = GCD(b, a mod b)。这个过程可以重复进行,直到余数为0,此时b就是最大公约数。在编程中,...

    利用三种算法求最大公约数

    在计算机科学和编程领域,求解最大公约数(Greatest Common Divisor,GCD)是一项基本的任务,它在数学和算法设计中具有广泛的应用。本文将深入探讨三种不同的方法来计算两个整数的最大公约数:分解质因数法、连续...

    算法试验一-求最大公约数实验报告-.pdf

    3. **欧几里得算法(减法版本)**:这是基于欧几里得算法的一种实现,通过不断用较大数减去较小数,直至两者相等,得到的就是最大公约数。其时间复杂度为O(log n),效率较高。 实验中提供了每个算法的C语言实现,并...

    欧几里德算法求解多个数的最大公约数

    这个算法基于一个基本原理:两个正整数a和b(a&gt;b)的最大公约数与b和a除以b的余数的最大公约数相等。如果余数为0,则b即为最大公约数;否则,重复此过程,直到余数为0。这个过程可以简洁地表示为: gcd(a, b) = gcd...

    用递归算法实现两个整数最大公约数的计算

    在IT领域,尤其是在编程与算法设计中,递归算法是...通过本次分析,我们不仅学习了递归算法的基本原理,还掌握了其实现最大公约数计算的具体方法。在未来的学习和工作中,递归算法将会成为解决更多复杂问题的有力工具。

    最大公约数最小公倍数n-s盒图

    在计算机科学领域,最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)是两个基本的数学概念,它们在算法设计和数据分析中广泛应用。N-S盒图(NS-Box Diagram),又称诺依曼-...

    算法_用欧几里得算法求最大公因数_

    在计算机科学和算法设计中,求解两个或多个整数的最大公因数(Greatest Common Divisor, GCD)是一项基础且重要的任务。欧几里得算法,也称为辗转相除法,是解决这一问题的经典算法,其历史可以追溯到古希腊数学家...

    最大公约数——三种算法

    以下将详细介绍三种常见的求解最大公约数的算法:欧几里得法、循环测试法和质因数分解法。 1. **欧几里得法**: 欧几里得算法,又称为辗转相除法,是由古希腊数学家欧几里得提出的一种高效求解最大公约数的方法。...

    扩展欧几里德算法---

    4. **最大公因数的分解**:通过扩展欧几里德算法,可以找到两个数的最大公约数的特殊分解形式,这对于理解数的结构和进行数论操作非常有用。 **四、算法效率** 欧几里德算法和扩展欧几里德算法的时间复杂度都为O...

    117、1627:【例 3】最大公约数--2020.04.13a.pdf

    根据给定的信息,本文将对最大公约数(Greatest Common Divisor, GCD...对于学习C++语言和参加NOIP(全国青少年信息学奥林匹克联赛)等竞赛的学生来说,掌握高精度计算方法和最大公约数算法是非常重要的基础技能之一。

    算法:n个数的最大公约数

    最大公约数在数学和计算机科学中有着广泛的应用,例如简化分数、分解质因数以及优化计算过程。 **1. 递归求n个数的最大公约数** 递归是一种解决问题的方法,它通过调用自身来解决更小规模的问题。求解n个数的最大...

    算法分析求最大公约数

    【算法分析求最大公约数】涉及的是在编程领域中如何高效地找到两个正整数的最大公约数(Greatest Common Divisor, GCD)。本实验旨在通过C++编程语言,设计并分析不同算法的效率,同时结合时间复杂性的理论进行实际...

    求最大公约数的三种算法

    本篇将详细介绍三种不同的方法来求两个自然数m和n的最大公约数:欧几里得算法、分解质因数法以及连续整数检测法。 1. **欧几里得算法**: 欧几里得算法,又称辗转相除法,是公元前3世纪由古希腊数学家欧几里得提出...

    算法-求最小公倍数和最大公约数的方法.rar

    它的基本思想是:对于任意两个正整数a和b(a&gt;b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。 欧几里得算法的伪代码如下: ``` function gcd(a, b): if b == 0: return a else: return gcd(b, a ...

    Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

    在计算机编程中,特别是在使用Python语言进行开发时,经常需要对两个数值进行最大公约数(GCD)和最小公倍数(LCM)的计算。最大公约数是指两个或多个整数共有约数中最大的一个,而最小公倍数是指能被两个或多个整数...

    递归算法求两个数的最大公约数

    ### 递归算法求两个数的最大公约数 #### 1. 递归方法解析 **递归算法**是一种解决问题的方法,其中函数通过调用自身来解决问题。递归算法的关键在于找到一个基本结束条件(base case),以及如何将问题分解成更小...

Global site tag (gtag.js) - Google Analytics