互いに既約な数について

[nanase]

x, y, z は1 から100 までの整数から選ばれるとして，
x * x + y * y = z * z
を満たす(x, y, z) の組み合わせをすべて求めて表示するプログラムを作成せよ．ただし，x, y は
x ≦ y の関係があるものに限る．

さらにx,y,z が互いに既約な(公約数をもたない) 組み合わせだけを表示するプ
ログラムに挑戦してみよ．
という問題がだされたのですが、

#include <stdio.h>
#include <math.h>

#define NUM_MAX 100.0

int main(void)

{
double x, y, z;

for (x = 1.0; x < NUM_MAX; x++) {
for (y = 1.0; y < NUM_MAX; y++) {
if (x >= y)
continue;

z = sqrt(x * x + y * y);
if (z == ceil(z))
printf(" X = %2.0lf, Y = %2.0lf, Z = %2.0lf\n", x, y, z);
}
}
return 0;
}

ここまでしかわからずここからどうすれば既約の数を除けるかわかりません。
すいませんが教えてもらえないでしょうか。

[みけCAT]

ソースコードを提示する際はBBCodeを有効にした(無効にしない)状態でcodeタグで囲んでいただけると、見やすくてありがたいです。

ここまでしかわからずここからどうすれば既約の数を除けるかわかりません。
すいませんが教えてもらえないでしょうか。

任意の2個の正の整数は公約数1をもつので、既約な(公約数をもたない)組み合わせはありません。よって、全ての組み合わせを除けば既約の数を除けます。

もしも2以上の公約数をもつ組み合わせのみを除きたいのであれば、ユークリッドの互除法などで最大公約数を求め、
最大公約数が1でない組み合わせを除けばいいでしょう。
aとbの最大公約数をgcd(a,b)とすると、a,b,cの最大公約数はgcd(a,gcd(b,c))で求められます。

[nanase]

ありがとうございます。
２以上の公約数を持つ場合を除きたいのでユークリッドの互除法を調べて
挑戦してみます。

ソースコードについては次回からは気を付けます。
ご指摘ありがとうございました。

[box]

x, y, z は1 から100 までの整数から選ばれるとして，

と言っているにもかかわらず、実際には

コード:

    double x, y, z;

double型を使っています。矛盾していませんか？

コード:

    for (x = 1.0; x < NUM_MAX; x++) {
        for (y = 1.0; y < NUM_MAX; y++) {

100を含まないようになっている点も、題意と矛盾していませんか？
また、double型の数に++演算子を適用して大丈夫なんでしょうか。
少なくとも私はやったことがありません。

[nanase]

ご指摘ありがとうございます。
私なりに書き換えてみました。
#include <stdio.h>
#include <math.h>

#define NUM_MAX 101.0

int main(void)

{
int x, y;
double z;

for (x = 1.0; x < NUM_MAX; x++) {
for (y = 1.0; y < NUM_MAX; y++) {
if (x >= y)
continue;

z = sqrt(x * x + y * y);
if (z == ceil(z))
printf(" X = %2.0d, Y = %2.0d, Z = %2.0lf\n", x, y, z);
}
}
return 0;
}

これなら大丈夫ですかね？

[box]

何で平方根が出てくるのかが謎です。
素直に

コード:

    if (x * x + y * y == z * z) {
        // 題意を満たしている
    }

とかいう風に書けばいいものを…
sqrtやceilを持ち出してきている結果、わざわざややこしく書いているように思えてなりません。

[nanase]

ありがとうございます。
難しく考えすぎてました。すいません。

ｘ、ｙ、ｚが公約数を持たないようにするプログラムがやっぱりよくわかりません。
ユークリッドは調べたんですがどのようにして今のプログラムに付け加えればいいかわかりません。
すいませんが詳しく教えてもらえないでしょうか。

[box]

x, y, zが互いに既約な数、という条件はいったんわきへどけておいて、
とりあえず
x * x + y * y == z * z
という条件を満たす(x, y, z)の組（ただし、x, y, zはいずれも1～100の整数で、x ≦ yの条件を満たす）を
求めることに専念してみてはどうでしょうか。
x, y, zが互いに既約な数を求めるのはその後で十分。

さて、
z * z = x * x + y * y > x * x より、z > x
z * z = x * x + y * y > y * y より、z > y
x ≦ yを加味して、x ≦ y < z … (1)
さらに、zがたかだか100であることを考え合わせると、x * x + y * yは10000を超えません。 … (2)
(1)(2)を考えに入れれば、ムダな計算がかなり省けそうです。

[nanase]

わかりました。
考えてみます。

[box]

わざとC以外の言語で書いて煙に巻くなど

コード:

def gcd(m, n)
  m, n = n, m if m < n
  return m if n == 0
  gcd(n, m % n)
end

def kiyaku?(x, y, z)
  return false if gcd(x, y) != 1 || gcd(y, z) != 1 || gcd(z, x) != 1
  true
end

N = 100
1.upto(N) do |x|
  x.upto(N) do |y|
    break if (t = x * x + y * y) > N * N
    (y + 1).upto(N) do |z|
      if t == z * z && kiyaku?(x, y, z)
        printf("%d^2 + %d^2 = %d^2\n", x, y, z)
      end
    end
  end
end