• ベストアンサー
  • 困ってます

最大公約数を求める

一般に、a,bが2^nくらいの整数であれば、最大公約数を求めるには、割り算も含めてn^3に比例した計算量が必要であるといわれている。しかし、これを素因数分解して求めると、素因数分解するのに、その数の平方根までの割り算が必要になるので、(√2)^nに比例した計算量が必要になる。 という説明があったのですが、”素因数分解するのに、その数の平方根までの割り算が必要になる”というのがよく分かりません。何故平方根まで割り算しないとならないのでしょうか????

共感・応援の気持ちを伝えよう!

  • 回答数3
  • 閲覧数112
  • ありがとう数0

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.2

簡単な数字で約数を考えてみてください.たとえば 96 では,約数は,    1,2,3,4,6,8,12,16,24,32,48,96 の 12 個です.そしてこれを両端から選んでいくと,積が元の数に一致することはご存知でしょう.つまり,    1×96 = 96,    2×48 = 96,    3×32 = 96,……. といったようにです.だからまず小さい約数 1 が分かれば 96 も約数だと分かります.2 が見つかれば 48 もそうです.3 が約数だから 32 もそうだ,という具合で,全部見つかるわけです.今回の場合は 1, 2, 3, 4, 6, 8 まで見つかれば,もう片方も決まるから,この六個だけの試験で約数が全部見つかったわけです. さて小さいほうから 8 まで六個だけ見つければいいことは理解いただけたと思います.実はその「どこまで探せばよいか」が平方根となっていることにお気づきでしょうか.√96 はだいたい 9.80 ですが,真ん中の 8 と 12 の間にあります.つまり,    1,2,3,4,6,8 | √96 | 12,16,24,32,48,96 のように真ん中が平方根で,8 と 12,6 と 16,というふうに全部が対になっているから,平方根の手前の自然数 9 まで確認すれば大丈夫だということです.だってそれ以降はもう見つかっているんですから. どの自然数でも約数を見つける際に同じような具合でできますから,平方根 (の一歩手前) まで割り算をすればいいのです.

共感・感謝の気持ちを伝えよう!

関連するQ&A

  • 最大公約数

    素因数分解を使わない最大公約数の求め方で、二つはユークリッドの互除法を利用するというのはわかったのですが、3つはどのようにして求めればいいと思いますか?

  • 素因数分解で最小公倍数・最大公約数がわかるのは何故?

    この年齢になって、ちょっと恥ずかしいのですが 素因数分解について質問があります。 なぜ素因数分解で「最小公倍数」や 「最大公約数」がわかるのでしょうか? 最大公約数の場合、例えば8と12だと  2)8 12   ーーーーーー  2)4  6   ------    2  3  8=2x2x2 12=2x2x3 となり、どちらの数にも縦軸の2x2が共通だから 4が最大公約数になる、というのはわかるんですけど なんか、いまいち説明になってないような気もします。 2、12、16で最小公倍数を求めた場合  2)8 12 16   ------ーー  2)4  6  8    --------   2)2  3  4   --------     1  3  2  8=2x2x2 12=2x2x3 16=2x2x2x2 なぜ2x2x2x1x3x2で答えを出すことが 出来るのかわかりません。 いろいろ考えてはみたんですが・・・(^^: 猿にも理解出来るよう、教えて頂けないでしょうか?

  • 最大公約数

    最大公約数をだしたいとき、整数なら因数分解すればいいのは分かるんですが例えばax+b,cx+dの最大公約数を求めるようなときはどうすればよいのですか?

その他の回答 (2)

  • 回答No.3
  • zk43
  • ベストアンサー率53% (253/470)

自然数nが合成数として、n=abと自然数の積で表わされるとする。 a≦bとすると、n≧aa=a^2より、√n≧a すなわち、nは必ず√n以下の素因数を持つ。 √n以下の数で割り切れなければ、nは素数である。 というような意味かと思うのですが。

共感・感謝の気持ちを伝えよう!

  • 回答No.1
  • koko_u_
  • ベストアンサー率18% (459/2509)

単純に 2で割る、3で割る、4で割る、… と繰り返して、素因数を見付けるのに、最悪 [√a] まで作業を繰り返す必要があるから。

共感・感謝の気持ちを伝えよう!

関連するQ&A

  • 最大公約数について

    「a,b,c,rが正の整数で、a=rb+cであるとき、a,bの最大公約数とb,cの最大公約数は一致することを証明せよ。」 という問題の解答の出だしが、 「aとbの最大公約数をm、bとcの最大公約数をnとおくと a=mA, b=mB(AとBは互いに素な整数) b=nB',c=nC(B'とCは互いに素な整数) と書ける」 となっているのですが、なぜこう書けるのかわかりません。 「a=mA, b=mB」「b=nB',c=nC」とかけるのはわかりますが、なぜAとB,B'とCが互いに素と言えるのかわかりません。 思いつく反例を上げると、a,b,cは異なる数とは問題文に書かれていないので、もしaとbが同じ数だとしたらA=Bとなり互いに素ではありませんよね?

  • 素因数分解で最大公約数、最小公倍数を求める方法

    例えば  24と18を使って素因数分解すると 2 |24 18 3 |12  9    4 3 となって共通の素因数をかけて6が最大公約数 共通の素因数と、共通の素因数を抜いた数を掛けて 72が最小公倍数 というふうに求めますが これは素数である必要はあるのですか? 別に 6| 24 18    4  3 として求めても同じではないのですか? 下の方法で何か困ることはあるのでしょうか?

  • 高校数学 最大公約数,最小公倍数

    問題. 3つの自然数45,63,n の最大公約数が9,最小公倍数が3150であるとき,nを求めよ なんですが,いろいろ素因数分解とかやってみて考えてみたのですが解けません. どなたか,解説してほしいです. よろしくお願いします..

  • 最大公約数の出し方

    大人ですが、最大公約数の出し方につまってしまいました。 12 72 108 3数の最大公約数を求めるため因数分解 2 |12 72 108 2 |6  36  54 3 |3  18  27 3 |1   6   9    1   2   3 最大公約数=2x2x3x3=36  げっ。 正解は12のはずなのに...。 本来は最後の3のところがいらないと思うのですが、なんて説明して いいかわかりません。こどもに。 わかるかた教えてください。なっとく次第締め切ります。

  • 最大公約数に関する問題です。

    最大公約数に関する問題です。 『2つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』という問題です。最大公約数は1と求められたのですが、後半の『(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』は、X,Y の組み合わせが無数にあると思うのですが、どうしたら良いのでしょうか?宜しくお願い致します。

  • 3数の最大公約数

    2つの整数の最大公約数は分かるのですが、3つの整数の最大公約数は分かりません。 ご教授宜しくお願いします。

  • 最大公約数を見つけたい

    C++初心者です。Visual studio 2005を用いてvisual C++の計算フォームアプリケーションを作りたいのです。 2ヶ所のテキストボックスに整数を入力させ、「実行」ボタンを押すとその2つの整数の最大公約数を出力させたいのですが、どうも上手くいきません。 できるだけ簡素なコードで最大公約数を見つけるにはどうすればいいでしょうか? どうかよろしくお願いいたします。

  • 最大公約数について!

    二つの整数m、n(m>n)の最大公約数をgとすると、mをnで割ったあまりとnとの最大公約数もgであることを証明せよ ただしm、nが互いに素であるとき、nとm-nも互いに素であることを使ってもよい はじめから解説をお願いします!

  • 最大公約数について教えてください!

    二つの整数m、n(m>n)の最大公約数をgとすると、mをnで割ったあまりとnとの最大公約数もgであることを証明せよ ただしm、nが互いに素であるとき、nとm-nも互いに素であることを使ってもよい 解説お願いします!

  • 最小公倍数と最大公約数でわからないことがあります

    例えば24と20という数字があって この二つの共通の素因数2でわると それぞれ12と10 さらに共通の素因数2でわると それぞれ6と5 6と5は互いに素 この素因数を掛けて 2×2=4 最大公約数4 互いに素の6と5を掛けて6×5=30 この30を共通の素因数の2×2 をかけて120 この120が最小公倍数 となると参考書に書いてあるのですが なぜこのような計算をして最大公約数と最小公倍数を求めてることが出来るのでしょうか? センター試験のために数Aの勉強をしているのですが そこまで考えずに、この計算をすると、それが求められるのだと 丸暗記するしかないでしょうか? 出来れば理解をしたいと思っています。よろしくお願いします。 あまり数学が得意ではないので簡単な表現で説明していただけると助かります。