0

誰かが与えられた2つの数の最低公約数（1を除く）を計算するためのいくつかの速い方法を提案できますか？1つの方法は、GCD（a、b）> 1であるかどうかをチェックし、素因数化（aおよびb）を行い、結果として最小公約数を選択することです。

これを行うためのより良い方法はありますか？

例：LCF（20,30）= 2、LCF（13,39）= 13

4

2 に答える 2

2

結局、両方を除算するか、またはに達するものが見つかるまで、両方の数を素数で除算しようとするよりも良いものはないと思います。sqrt(min(a,b))

于 2012-06-25T09:10:35.260 に答える
-1

2から値n/2にループするだけです。ここで、nは2つの数値のうち小さい方です。for（int i = 2; i <= n / 2; i ++）if（n％i == 0 && m％i == 0）break;のように条件をループに入れます。

iはあなたの必要な値です。

于 2012-06-25T09:46:09.310 に答える