官术网_书友最值得收藏!

8. Greatest common divisors

The most obvious way to calculate GCD(A, B) is to simply try all of the values smaller than A and B and see which ones divide both numbers. That method is straightforward and reasonably fast, although it could take a while if A and B are very large. In particular, using this method to find GCD(10370370276, 82962962964) could take a long time.

A faster alternative would be to factor A and B (I'll talk about factoring later in this chapter) and then determine the factors that they have in common.

An even faster alternative was described by Euclid (pronounced yoo-klid) around 300 BC. Because he first described the algorithm, it is called Euclid's algorithm or the Euclidean algorithm.

The idea behind the algorithm is that, if A > B and C evenly divides both A and B, then C must also evenly divide A – B. That leads to the following algorithm:

  1. Set remainder = A mod B
  2. If remainder is 0, then B is the GCD
  3. Otherwise set A = B and B = remainder, and then repeat from step 1

For example, the following steps show the calculation for GCD(180, 48):

  1. Remainder = 180 % 48 = 36
  2. A = 48, B = 36
  3. Remainder = 48 % 36 = 12
  4. A = 36, B = 12
  5. Remainder = 36 % 12 = 0
  6. At this point, the remainder is 0, so the GCD is B, which is 12

This calculation found GCD(180, 48) in only six steps.

The following method uses this algorithm to calculate the GCD:

// Use Euclid's algorithm to find GCD(a, b).
private long GCD(long a, long b)
{
a = Math.Abs(a);
b = Math.Abs(b);

// Pull out remainders.
for (;;)
{
long remainder = a % b;
if (remainder == 0) return b;
a = b;
b = remainder;
};
}

This code simply takes the absolute values of its inputs a and b, and then follows Euclid's algorithm.

It's interesting to see what happens if a < b when the algorithm starts. I'll let you work through that on your own.

Download the GCD example solution to see additional details.

主站蜘蛛池模板: 化州市| 商都县| 巢湖市| 白银市| 蒲城县| 海原县| 天津市| 墨竹工卡县| 满洲里市| 宝兴县| 吉首市| 尤溪县| 敦化市| 威宁| 仪陇县| 嘉祥县| 峨眉山市| 绵阳市| 新郑市| 视频| 大新县| 郧西县| 和平区| 洛宁县| 兴山县| 彭阳县| 宁化县| 冷水江市| 开江县| 喀什市| 新乡市| 深圳市| 沙坪坝区| 延庆县| 彩票| 体育| 肃北| 昌平区| 舟曲县| 蓝山县| 徐州市|