ProjectEulerを斬る！問9

Problem 9
25 January 2002

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^(2) + b^(2) = c^(2)

For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

ピタゴラス数の3つの組というものはa<b<cが成り立っていてかつa^2+b^2=c^2が成り立っている3つの数字の組を言います。
例えば、 3^2 + 4~2=9+16=25=5^2
a+b+c=1000を満たすピタゴラス数の３つの組が存在します。そのabcの積を求めなさい。
(日本語訳PNN)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int a = 0;
int b = 0;
int c = 0;
for (int n = 2; a + b + c != 1000; n ++)
{
for (int m = 1; m < n; m ++)
{
//nとmが互いに素かどうかを確かめる
bool b_coprime = true;
if ((int)(n / 2) * 2 == n && (int)(m / 2) * 2 == m)
{
b_coprime = false;
}
else
{
int p = m;
if ((int)(m / 2) * 2 == m)
{
for (int q = m; (int)(p / 2) * 2 == p;)
{
p /= 2;
}
}
for (int q = 3; q <= p; q += 2)
{
if ((int)(p/q)*q==p&&(int)(n/q)*q==n)
{
b_coprime = false;
}
}
}
/*確認
if (b_coprime == true)
{
Console.WriteLine(n.ToString() + "," + m.ToString() + ":" + b_coprime);
Console.ReadLine();
}*/

//mとnが同時に偶数、奇数である場合は計算しない
bool b_nm_oe = false;
if ((int)(n / 2) * 2 == n && (int)(m / 2) * 2 == m)
{
b_nm_oe = true;
}
if ((int)(n / 2) * 2 != n && (int)(m / 2) * 2 != m)
{
b_nm_oe = true;
}

if (b_coprime == true && b_nm_oe == false)
{
a = n * n - m * m;
b = 2 * n * m;
c = n * n + m * m;
Console.WriteLine(a.ToString() + "," + b.ToString() + "," + c.ToString() + ":" + (a + b + c).ToString());
Console.ReadLine();
}
}
}
Console.WriteLine(a * b * c);
}
}
}

???出てこないぞー、互いに素を求めるアルゴリズムは結構工夫したぞー。なんでかな～なんでかな～
なんかすっごく嫌な予感がするな～怖いな～やだな～
なんて思ったので組みなおしてみた。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int a = 0; int b = 0; int c = 0;
int req = 1000;
bool ans = false;
for (int i = 1; i <= req; i++)
{
for (int j = i + 1; j <= req; j++)
{
int k = req - i - j;
if (i * i + j * j == k * k)
{
if (i + j + k == req)
{
a = i; b = j; c = k;
ans = true;
}
break;
}
if (j > k)
{
break;
}
}
}
Console.WriteLine(a.ToString()+","+b.ToString()+","+c.ToString());
Console.WriteLine((a*b*c).ToString());
Console.ReadLine();
}
}
}

出力結果：31875000

結果的に言えば、互いに素とかややこしい事は一切考える必要はなかった。
というのは、この積が出るときのピタゴラス数が、200、375、425なのだ。
見た瞬間5が公約数にあることがわかる。

互いに素判定アルゴリズムなんていらんかったんや・・・
はあ、なんか疲れてきたけど、まあ、このアルゴリズムもいつかは役に立つだろう！
ポジティブポジティブｗｗｗ