ルジャンドルの公式:n! に含まれる素数の指数
100の階乗には素数5が24個含まれます。100を5で割ると20、20を5で割ると4で、20と4を足して24です。n と素数 p を入力すると、数回の割り算でこの指数を求めます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- N
- 100
- 電力(W)
- 5
- 指数
- 24
この計算機は、ルジャンドルの公式を用いて n の階乗に含まれる指定素数 p の指数を正確に返します。巨大な整数 n! を直接作らず、n を p で繰り返し割って整数商を合計します。と表します。 整除性、末尾のゼロ、二項係数、数論の学習、競技プログラミングに利用できます。入力は範囲内の整数か検証され、計算前に p の素数性も個別に確認されます。そのため合成数を指定すると、誤解を招く数値ではなく明確なエラーになります。
ルジャンドルの公式が数えるもの
この公式は積 1 × 2 × 3 × … × n に素数 p が何個含まれるかを数えます。p の倍数は1個、p² の倍数は追加で1個、p³ の倍数はさらに1個を与えます。したがって指数は floor(n/p) + floor(n/p²) + floor(n/p³) + 続く項で、商がゼロになれば終了します。
つまり 5²⁴ は 100!を割り切りますが、5²⁵ は割り切りません。応答には n と p も明記されます。
入力の検証と計算方法
必須項目は非負整数 n と 2 以上の素数 p です。10進数字だけの文字列は受け付けますが、分数、負数、空文字列、無限大、上限超過は拒否します。検証後、quotient = n を floor(quotient/p) で置き換え、その値をゼロまで指数へ加えます。
この方法は累乗のオーバーフローを避けます。
より大きな問題への応用
C(n, k) に含まれる p の指数は、n!の結果から k! と (n-k)!の結果を引いて求められます。
p^a が n! を割り切るのは、a が返された指数以下の場合だけです。10進数の末尾のゼロは 2 と 5 の組から生じるため、n!に含まれる 5 の指数が個数になります。
この機能は完全な素因数分解ではなく、指定した1つの素数へ簡潔に回答します。授業、自動採点、競技、バックエンド検証に適しています。複数の素数には、それぞれ1回ずつ実行してください。
活用例
階乗を割る最大の素数累乗を確認
階乗自体を計算せず、p^a が n! を割り切る最大の a を求めます。
二項係数の付値を評価
3つの階乗指数を組み合わせ、二項係数に含まれる p の指数を正確に求めます。
よくある質問
p はなぜ素数でなければなりませんか?
この形の公式は単一の素数の付値を求めるため、合成数は誤表示を防ぐ目的で拒否します。
p が n より大きい場合はどうなりますか?
1 から n のどの因子も p で割れないため、結果はゼロです。
100の階乗の末尾には0がいくつ並びますか?
24個です。末尾の0には2と5が1つずつ必要で、階乗には2の方が5より多く含まれるため、0の個数は5の指数と同じになり、100では24です。
二項係数に含まれる p の指数はどう求めますか?
n の階乗に含まれる p の指数から、k の階乗と (n − k) の階乗に含まれる指数を引きます。その差が、二項係数に含まれる p の指数になります。
この指数は何を意味しますか?
n の階乗を素因数分解したとき、素数 p が何回現れるかを表します。例えば100の階乗では5が24回現れるので、5の24乗では割り切れますが、それより1つ大きい指数では割り切れません。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/legendre-formula \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":100,"p":5}'const res = await fetch("https://api.kit.forhosting.com/numth/legendre-formula", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 100,
"p": 5
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/legendre-formula",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 100,
"p": 5
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/legendre-formula", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":100,"p":5}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":100,"p":5}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/legendre-formula", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"n": 100,
"p": 5
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.legendre_formula",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_n | 1000000000 |
max_p | 1000000000 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
結果は n! の p 進付値で、通常 v_p(n!)
ルジャンドルの公式が数えるもの
n = 100、p = 5 では 20、4、0 の合計が 24 です。n = 0 と n = 1 の階乗は 1 なので指数はゼロです。
入力の検証と計算方法
p = 7 は成功し、p = 9 は invalid_input になります。処理は決定論的で、通信も乱数も使わず、ブラウザーと API で同じ結果になります。成功した API リクエストの料金は $0.002 です。
連携の活用例
階乗の末尾のゼロを計算
p = 5 で n! の10進末尾ゼロを求め、他の素数累乗基数にも応用できます。
技術的な質問
指数は何を意味しますか?
p^a が n! を余りなく割り切る最大の整数 a です。
n の階乗を実際に作りますか?
いいえ。連続する整数商を合計し、巨大な階乗値を避けます。
API 計算の料金はいくらですか?
成功した API リクエスト1回は $0.002 です。ブラウザーも同じ決定論的処理を使います。