辗转相除法求最大公约数_JAVA_编程开发_程序员俱乐部

? ? ? ?

? ? ? 1.简介:

? ? ? ?辗转相除法， 又名欧几里德算法（Euclidean algorithm），求两个正整数的最大公约数的算法,辗转相除法在处理大数据时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍

? ? ?

? ? ? ?2.描述: 两个正整数a,b.

? ??
?

class="java">package sss;

import java.util.Scanner;

/**
 * 辗转相除法:利用以下性质来确定两个正整数 a 和 b 的最大公因子的.
 * 1. a ÷ b，令r为所得余数（0≤r<b）若 r = 0，算法结束；b 即为答案。
 *  2. 互换：置 a←b，b←r，并返回第一步
 * @author Administrator
 *
 */
public class ZhanZhuanDiv {

	public static void main(String[] args) {
		
		new ZhanZhuanDiv().Test();
	}
	
	
	public void Test(){
		Scanner scanner =new Scanner(System.in); //定义扫描器
		System.out.println("请输入两个正整数，并用英文逗号隔开");
		String getString =scanner.nextLine();//得到控制台输入的数据
		
		String[] sss=getString.split(",");//字符串进行分割
		int len =sss.length;
		int[] num= new int[len];
		for (int i = 0; i < sss.length; i++) {
			
			num[i]=Integer.parseInt(sss[i]);
		}
		int mm=sucDivison(num[0],num[1]);
		System.out.println("最大公约数是:"+mm);
		
	}
	
	public int sucDivison(int m,int n){
		int temp=0;
		if (m<n) {
			temp=m;
			m=n;
			n=temp;
		}
		
		//主要算法
		if (m%n==0) {
			return n;
		}
		else{

			return sucDivison(n,m%n);	
		}
		
		
	}
}

• 
• 大小: 13 KB

• 查看图片附件