![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
No.1ベストアンサー
- 回答日時:
素因数分解をするときに,割る数はどう決めるのですか?2,3,5,7,9,...と順に試すのですか?与えられた数が簡単な数ならばそれでもいいけど,効率が悪すぎです。
例えば879017と902801の最大公約数は何?
No.3
- 回答日時:
そう, 「素因数分解できる」なら, ユークリッドの互除法はいらない. そして, 小さい数であれば実際に素因数分解した方が速い.
ただ, 相手が大きくなると話が変わってくる. つまり, 「効率的に素因数分解する方法」は知られていないのに対してユークリッドの互除法は非常に効率的に実行できる. その結果,
1000桁の数の素因数分解を実行する
よりも
100000桁の 2つの数に対してユークリッドの互除法を実行する
方がはるかに簡単だったりする.
No.2
- 回答日時:
プログラマです。
プログラミングの世界では時たま結構桁数の大きい数の数の最大公約数を求める必要が出てきます。CPUは早いのでほとんどの場合人間の感覚では、ユークリッド互除法でも共通に割れる数を探す方法でもあまり差はないように感じる場合が多いですが、ユークリッド互除法の方が圧倒的に高速なのは間違いありません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 大学受験 整数問題 Nを正の整数とする。 N+18がN+2の倍数となるようなNの値の個数を求めたい。 解説に、 1 2022/08/13 12:25
- 数学 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分かりませ 2 2023/03/05 16:54
- 数学 再質問 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分 4 2023/03/05 17:08
- 数学 ユークリッド互除法なんですが最高公倍数が15なのは分かるんですけどrとsの解き方が分かりません。 教 4 2023/02/27 00:43
- 数学 ユークリッドの互除法 添付についてですが、g(24337, 158)=g(158, 5)=1 という 2 2022/10/24 14:43
- 計算機科学 高校1年の数学です! ユークリッドの互除法です。 写真の左上の問題で、問題集の答えは x=14、y= 1 2023/02/25 16:59
- 数学 最小公倍数と最大公約数の求め方で画像のような計算法があったのですが、理解できません。 なぜ2つ数24 4 2022/04/10 13:37
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
実数x.yについて、x-y=1のとき...
-
数学のユークリッドの原論はな...
-
ユークリッド互除法の意義
-
自然対数の含まれる計算式
-
さいころを2つ振るとき。出た...
-
【落窪物語「すれちがう思惑」】...
-
現代文 檸檬 梶井基次郎さんの...
-
卒業論文についての質問です。 ...
-
2つの数の積が1になるとき、一...
-
平家物語の「先帝身投げ」の部...
-
高校受験についてです。 分かる...
-
陸部の大会に出ない理由を考え...
-
4980円の10%オフって何円ですか?
-
上記のとおりお願いします って...
-
【パワハラの基準】「会議での...
-
目上の人に聞き返すにはどうし...
-
明日テストでこの問題が出ます ...
-
英語のレポートの字数制限が400...
-
神社でお願いしたことを人に言...
-
英語で筆算は何と言いますか
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学のユークリッドの原論はな...
-
実数x.yについて、x-y=1のとき...
-
関数 y=−2/1xの二乗について、...
-
Mathematicaで条件を変えてプロ...
-
フーリエ級数展開における交流...
-
(3) 3x³ ー 8x² + 46x − 60 = 0 ...
-
自然対数の含まれる計算式
-
数学 日本語では「以上」の対義...
-
何故②から最大公約数がq²だと分...
-
ユークリッド互除法の意義
-
拡張ユークリッド互助法
-
一次関数 切片
-
極大極小の問題について
-
(4)と(5)の解説と答え教えてほ...
-
極値からの関数決定問題につい...
-
至急 証明
-
三次方程式記述について
-
関数 関数とグラフ が良く分か...
-
反対称律について
-
2変数関数の極値について
おすすめ情報