最大公約数(GCD)計算ツール|ユークリッドの互除法
1071と462の最大公約数は21で、素因数分解をせずに、ユークリッドの互除法の3回の割り算で求まります。負の数や0を含む2つの整数を入力でき、結果を使えば462/1071を22/51に約分できます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- A
- 1,071
- B
- 462
- Gcd
- 21
符号は無視され、片方が0の場合は gcd(n, 0) = |n| の規則で処理されます。拒否されるのは数学的に未定義の gcd(0, 0) のみです。テスト中に表示される数値が、そのまま本番のパイプラインに届く数値です。
最大公約数とは何か
2つの整数の最大公約数とは、両方をちょうど割り切れる最大の正の整数です。1071 と 462 の場合は 21 です。1071 = 21 × 51、462 = 21 × 22 であり、これより大きな整数で両方を割り切れるものはありません。
結果が 1 のとき、2つの数は互いに素と呼ばれ、共通の因数をまったく持ちません。この概念は古く、ユークリッドの『原論』の中心に位置づけられていますが、分数を約分する、2つの周期的処理が一致するか確かめる、比率を表示前に簡単にするなど、実務的な問いに今も最速で答えます。近似も丸めもありません。
整数を入れれば、正確な整数が返ります。
ユークリッドの互除法の仕組み
実装は減算を使わないユークリッドの方式です。大きい数を小さい数で割った余りで置き換える操作を、余りが 0 になるまで繰り返し、最後の 0 でない余りが答えです。1071 と 462 なら、1071 mod 462 = 147、462 mod 147 = 21、147 mod 21 = 0 となり、結果は 21 です。
ループは O(log min(a, b)) 回で済むため、安全整数の上限に近い数値でも数ステップで終わり、因数分解も浮動小数点も使いません。割り切れるかどうかは符号に依存しないため、先に符号を取り除きます。したがって gcd(-12, 18) は 6 です。
境界ケースは標準の慣例に従います。
実務での活用場面
分数の約分が代表的な用途です。分子と分母を最大公約数で割れば既約分数になり、請求エンジン、レシピの分量調整、比率の表示などで数値を提示する前に必要とされます。また、結果が 1 かどうかで調べる互いに素の判定や、暗号で使われる中国剰余定理やモジュラ逆数の仕組みの基礎でもあり、最大公約数は拡張ユークリッドの互除法の第一歩です。
この機能はエッジ上で動作し、何も保存されません。2つの整数が届き、約数が返るだけで、数値の記録は残りません。
活用例
分数を既約分数に約分する
比率を保存・表示する前に分子と分母を最大公約数で割れば、462/1071 は 22/51 になります。
2つの数が互いに素か判定する
結果が 1 なら2つの数は共通の因数を持ちません。スケジューリング、ハッシュ、暗号の多くの構成で前提となる条件です。
周期的な処理を一致させる
最小公倍数と組み合わせれば、長さの異なる2つの周期がいつ一致するか、作業を等しいバッチに分ける方法が分かります。
よくある質問
入力に負の数は使えますか?
はい。 割り切れるかどうかは符号に依存しないため、符号は無視されます。gcd(-12, 18) は常に正の整数 6 を返します。
0 の場合はどうなりますか?
0 でない任意の n について gcd(n, 0) は |n| を返します。(
整数はどのくらいの大きさまで使えますか?
JavaScript の安全整数、つまり絶対値で 2^53 − 1 までです。その範囲外の値は、不正確に計算するのではなく拒否されます。
どのアルゴリズムを使っていますか?
ユークリッドの互除法です。余りが 0 になるまで剰余計算を繰り返します。O(log min(a, b)) 回で動作し、因数分解も浮動小数点も使いません。
最大公約数が1になるとはどういうことですか?
2つの数が互いに素で、1以外に共通の約数をもたないという意味です。そのような2数でできた分数はそれ以上約分できず、多くの暗号の計算でもこの性質が前提として確かめられます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/math/gcd \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/gcd", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/gcd",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/gcd", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/gcd", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"a": 1071,
"b": 462
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.gcd",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
最大公約数APIは、2つの整数を受け取り、両方を余りなく割り切れる最大の正の整数を、古典的なユークリッドの互除法で求めて返します。小さく正確なツールで、ブラウザで無料で動くコードと有料エンドポイントのコードは同一です。
最大公約数とは何か
このエンドポイントは a と b の2つの整数を受け取り、符号はどちらでも受け付け、正の約数を1つのオブジェクトで返します。
ユークリッドの互除法の仕組み
0 でない任意の n について gcd(n, 0) = |n| であり、gcd(0, 0) は未定義のため、黙って誤った 0 を返すのではなく invalid_input エラーで拒否されます。
実務での活用場面
このページではAPIと同じコードで無料で試せます。ご自身のシステムから呼び出す場合のみ1リクエスト$0.002をお支払いいただくため、何百万組も処理するデータクレンジング処理に組み込んでも十分に安価です。
技術的な質問
料金はいくらですか?
1リクエスト$0.002です。このページではまったく同じコードをブラウザで無料で実行できます。