ピタゴラスの定理(a^2=b^2+c^2)を満たすa,b,cを求めるのですが、
条件として、bとcは100未満であること、b<cの関係が成り立っていること、a,b,cは互いに素であるというととです。
3重ループを使用して、ピタゴラスの定理を作ることはできたのですが、どうしても互いに素という部分がわかりません。
よろしくお願いします。
互いに素について
Re: 互いに素について
(Wikipediaより転載)互いに素(たがいにそ、英: coprime)は、2つの整数が 1 と −1 以外に公約数を持たない場合の2数の関係である。これは2つの整数の最大公約数が 1 であることと同値である。2つの整数 a, b が互いに素であることを、記号で a ⊥ b と表すこともある。
3つの整数 a, b, c について、a と b、b と c、c と a の公約数がそれぞれ 1 と −1 のみでなくても、a, b, c の公約数としては 1 と −1 のみのときがある(例:a = 6, b =15, c = 10)。このようなとき、a, b, c は互いに素という。一般のn個の整数についても同様に定義される。
2整数の少なくとも1つが大きい場合、互いに素であるかどうかを知るのに、素因数分解による方法では、一般には困難である。素因数分解をせずに最大公約数を求める最良のアルゴリズムである、ユークリッドの互除法がある。これにより、最大公約数が 1 であれば互いに素、2 以上ならば互いに素ではないことが分かる。
というわけで、a,b,cの最大公約数を求め、1なら互いに素、2以上なら互いに素ではないと判定できます。
2個の数の最大公約数は、ユークリッドの互除法を用いると簡単に求めることができます。
3個の数の最大公約数を求めるには、まずその中の適当な2個の数の最大公約数を求め、その2個の数の最大公約数と残りの1個の数の最大公約数を求めればいいです。
オフトピック
ピタゴラスの定理とよく似た問題ですが、
時期も離れているし、コードの方針も違うので、さすがに同一人物ではないですよね…。
時期も離れているし、コードの方針も違うので、さすがに同一人物ではないですよね…。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 互いに素について
とりあえず、互いに素という条件を外した時、a,b,cを求めて出力するコードをここに貼ってください。momon さんが書きました:出来れば、具体的に教えてください。
また、「定義や最大公約数単体」のコードも貼ってください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 互いに素について
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 互いに素について
もっとちゃんと考えて、ムダな計算をしなくてすむようにしましょう。aが399になることは、bとcの条件からありえないですよね。momon さんが書きました:それぐらいの数字であれば問題ないと思ったからです。
この条件があるということは、momon さんが書きました:bとcは100未満であること、b<cの関係が成り立っている
bは最大98、cは最大99になる可能性があるということです。
ということは、aは最大いくつになる可能性がありますか?
今回の問題では最大2桁ですからまだいいですが、仮に、もっと多くの桁数で
ピタゴラスの定理 a^2 == b^2 + c^2 を満たすa, b, cを見つけようとする際、
aの範囲をいいかげんに決めているとムダなパワーを消費していることになります。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 互いに素について
最初のコードの3重ループにおいて、
i == 0
ならば、そのときのa, b, cはピタゴラスの定理を満たしていますね。
ただし、この時点ではa, b, cが互いに素(a, b, cの最大公約数が1)であるかどうかはわかりません。
そこで、a, b, cを引数としてa, b, cの最大公約数を求める関数(※)を用意します。
この関数の中では、
a, bの最大公約数を求める(これは2数の最大公約数だからできているんですよね?)
と
「a, bの最大公約数(計算済)」とcの最大公約数を求める(これも2数の最大公約数だからできているんですよね?)
とを実行すればよいです。
(※)の戻り値が1、つまり、a, b, cが互いに素ならば、出力すればよいです。
i == 0
ならば、そのときのa, b, cはピタゴラスの定理を満たしていますね。
ただし、この時点ではa, b, cが互いに素(a, b, cの最大公約数が1)であるかどうかはわかりません。
そこで、a, b, cを引数としてa, b, cの最大公約数を求める関数(※)を用意します。
この関数の中では、
a, bの最大公約数を求める(これは2数の最大公約数だからできているんですよね?)
と
「a, bの最大公約数(計算済)」とcの最大公約数を求める(これも2数の最大公約数だからできているんですよね?)
とを実行すればよいです。
(※)の戻り値が1、つまり、a, b, cが互いに素ならば、出力すればよいです。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。