互いに素について

[momon]

ピタゴラスの定理（a^2=b^2+c^2）を満たすa,b,cを求めるのですが、
条件として、bとcは100未満であること、b<cの関係が成り立っていること、a,b,cは互いに素であるというととです。

3重ループを使用して、ピタゴラスの定理を作ることはできたのですが、どうしても互いに素という部分がわかりません。
よろしくお願いします。

コード:

#include<stdio.h>
int main(void)
{
	int a, b, c,i,j;

	for (a = 1; a < 400;a++){
		for (b = 1; b < 100; b++){
			for (c = 1; c < 100; c++){
				if (b < c){
					i = b*b + c*c - a*a;
				}
			}
		}
	}

	return 0;
}

[みけCAT]

互いに素（たがいにそ、英: 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 以上ならば互いに素ではないことが分かる。

(Wikipediaより転載)

というわけで、a,b,cの最大公約数を求め、1なら互いに素、2以上なら互いに素ではないと判定できます。
2個の数の最大公約数は、ユークリッドの互除法を用いると簡単に求めることができます。
3個の数の最大公約数を求めるには、まずその中の適当な2個の数の最大公約数を求め、その2個の数の最大公約数と残りの1個の数の最大公約数を求めればいいです。

オフトピック

ピタゴラスの定理とよく似た問題ですが、
時期も離れているし、コードの方針も違うので、さすがに同一人物ではないですよね…。

[momon]

定義や最大公約数単体ではできるのですが、他の文と組み合わせになると全く手が付かないのです。
出来れば、具体的に教えてください。

[みけCAT]

出来れば、具体的に教えてください。

とりあえず、互いに素という条件を外した時、a,b,cを求めて出力するコードをここに貼ってください。
また、「定義や最大公約数単体」のコードも貼ってください。

[box]

コード:

	for (a = 1; a < 400;a++){

aが400未満であると限定できる理由は何ですか？

[momon]

それぐらいの数字であれば問題ないと思ったからです。

[box]

それぐらいの数字であれば問題ないと思ったからです。

もっとちゃんと考えて、ムダな計算をしなくてすむようにしましょう。aが399になることは、bとcの条件からありえないですよね。

bとcは100未満であること、b<cの関係が成り立っている

この条件があるということは、
bは最大98、cは最大99になる可能性があるということです。
ということは、aは最大いくつになる可能性がありますか？
今回の問題では最大2桁ですからまだいいですが、仮に、もっと多くの桁数で
ピタゴラスの定理 a^2 == b^2 + c^2 を満たすa, b, cを見つけようとする際、
aの範囲をいいかげんに決めているとムダなパワーを消費していることになります。

[box]

最初のコードの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が互いに素ならば、出力すればよいです。