计算两个数的最大公因子

 

给定两个正整数m和n，求它们的最大公因子，即能够同时整除m和n的最大正整数。

E1.【求余数】 以n除m并令r为所得余数。（我们将有0<=r<n）

E2.【余数为零？】若r=0,算法结束，n即为答案。

E3.【减少】置mß---n,nß-r,并返回步骤E1

 

 

package com.javaeye.rsrt;

/**
 * @description 求两个数的最大公因子
 * @author nishiting
 * @date 2010-9-15
 */
public class CommonFactor {

	/**
	 * @param arags
	 */
	public static int result=0;
	public static void main(String[] args) {

		int a = 77;
		int b = 21;
		
		CommonFactor cf = new CommonFactor();
		cal c = cf.new cal();
		c.calculate(a, b);
		System.out.println(a + "与" + b + "的最大公因子为：" + ((Integer)result).toString());
	}

	private class cal {

		public cal() {

		}

		public void calculate(int a, int b) {

			// 如果a比b小，那么a与b交换
			if (a < b) {
				int temp = a;
				a = b;
				b = temp;
			}

			if (a % b == 0) {
				result = b;
			} else {
				int r = a % b;
				a = b;
				b = r;
				calculate(a, b);
			}
		}
	}

}

评论

8 楼 若是人间 2010-09-16  

lyw985 写道

public class Test{
	public static void main(String[] args) throws Exception {
		int a = 24, b = 42;
		System.out.println(get(a, b));
	}
	public static int get(int a, int b) {
		return a % b == 0 ? b : get(b, a % b);
	}
}

取模时要注意ab的大小关系，三目运算的效率应该跟if else没什么再样吧，这样写没什么意义

7 楼 lyw985 2010-09-16  

public class Test{
	public static void main(String[] args) throws Exception {
		int a = 24, b = 42;
		System.out.println(get(a, b));
	}
	public static int get(int a, int b) {
		return a % b == 0 ? b : get(b, a % b);
	}
}

6 楼 若是人间 2010-09-16  

anderkey 写道

// 如果a比b大，那么a与b交换  
            if (a < b) {  
                int temp = a;  
                a = b;  
                b = temp;  
            }  
错了吧？

呵呵，写错了

5 楼 anderkey 2010-09-16  

// 如果a比b大，那么a与b交换  
            if (a < b) {  
                int temp = a;  
                a = b;  
                b = temp;  
            }  
错了吧？

4 楼 若是人间 2010-09-15  

landman 写道

这里是递归，还有别的办法吧

知道了怎么算，程序怎么实现那是有多种方法的，三楼用while循环就不错

3 楼 landman 2010-09-15  

#include<stdio.h>

int main(void)
{
int m, n, k, tmp;
printf("Input 2 integers:\n");
scanf("%d %d", &m, &n);

if(m<n)
{
  tmp=m;
  m=n;
  n=tmp;
}

while(1)
{
  k=m%n;
  if(0==k)
  {
   printf("The largest public-factor: %d\n", n);
   return 0;
  }
  else
  {
   m=n;
   n=k;
  }
}
}

2 楼 landman 2010-09-15  

这里是递归，还有别的办法吧

1 楼 指尖旋律 2010-09-15