问题5－求能被1到20所整除的最小的数

    问题叙述如下：
    “2520是最小的数能够整除1到10，求能被1到20所整除的最小的数？”
  代码如下：

 

	/**
	 * 数字i从m到n，遍历，如果i不能被result整除，我们就将i除以i与result的最大公约数，并与当前result想乘
	 *
	 */
	private static int getNumber(int m, int n) {
		int result = n;
		for (int i = n - 1; i >= m; i--) {
			if (result % i != 0) {
				result *= i/gcd(result,i);
			}
		}
		return result;
	}

	/**
	 * 最大公约数：欧几里德算法 定理：gcd(a,b) = gcd(b,a mod b)
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcd(int a, int b) {
		if (b != 0)
			return gcd(b, a % b);
		else
			return a;
	}

 

    调用getNumber(1,20)即可得到答案232792560。
    由于在此用到最大公约数，所以在下面给出了一些实现。

 

	/**
	 * 最大公约数：欧几里德算法
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcd1(int a, int b) {
		if (a > b) {
			gcd1(b, a);
		}
		int temp = 0;
		for (; b != 0;) {
			temp = a % b;
			a = b;
			b = temp;
		}
		return a;
	}

	/**
	 * 最大公约数：Stein算法 gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，
	 * 特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcdByStein(int a, int b) {
		if (a > b) {
			gcdByStein(b, a);
		}
		if (b == 0) {
			return a;
		}
		if (a % 2 == 0 && b % 2 == 0) {
			return 2 * gcdByStein(a / 2, b / 2);//a,b都是偶数
		}
		if (a % 2 == 0) {
			return gcdByStein(a / 2, b);//仅a为偶数
		}
		if (b % 2 == 0) {
			return gcdByStein(a, b / 2);//仅b为偶数
		}
		return gcdByStein((a + b) / 2, (a - b) / 2);//a,b都是奇数
	}

 

    如果有其他的方法，也请贴出大家一起讨论。^_^
    请不吝赐教。
    @anthor ClumsyBirdZ