Legendre formula calculator
The prime 5 appears 24 times in the factorial of 100: 100 divided by 5 gives 20, 20 divided by 5 gives 4, and 20 plus 4 makes 24. Enter any n and prime p to get that exponent in a few divisions. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 100
- Power (W)
- 5
- Exponent
- 24
This Legendre formula calculator returns the exact exponent of a chosen prime p in n factorial. Instead of constructing the enormous integer n!, it repeatedly divides n by p and adds the integer quotients. Every input is checked as a bounded whole number, and p is independently tested for primality before the calculation begins, so a composite base produces a clear validation error rather than a misleading answer.
What Legendre's formula measures
Legendre's formula counts how many copies of a prime p occur in the product 1 × 2 × 3 × … × n. Every multiple of p contributes at least one copy, every multiple of p² contributes an additional copy, and every multiple of p³ contributes another. Therefore the exponent is floor(n/p) + floor(n/p²) + floor(n/p³) + so on, with the sum ending when the quotient becomes zero.
The calculator returns that exponent directly and never expands the factorial. This distinction matters because factorial values grow extremely quickly, while the number of divisions required by the formula grows only logarithmically.
How inputs are validated and calculated
Send two required fields: n, a non-negative whole integer, and p, a prime whole integer of at least 2. Numeric strings containing only decimal digits are accepted by the core calculation as a convenience, but fractions, signs on negative values, empty strings, infinities, and values beyond the published bound are rejected. The service also checks that p is genuinely prime.
After validation, the implementation starts with quotient = n. It replaces the quotient with floor(quotient/p), adds that value to the exponent, and repeats until the quotient reaches zero. This quotient-based form is mathematically identical to calculating successive powers of p, but it avoids multiplying powers that could overflow.
Using the exponent in larger problems
The returned exponent is a compact building block for many number-theory workflows. To find the exponent of p in a binomial coefficient C(n, k), calculate the exponent in n! and subtract the exponents in k!
and (n-k)!. To test whether a power p^a divides n!, compare a with this response: divisibility holds exactly when a is no greater than the returned exponent. Trailing zeros are another familiar application. In base ten they arise from pairs of 2 and 5, and factorials contain more factors of 2 than 5, so the exponent of 5 in n!
gives the number of trailing decimal zeros. Similar reasoning works for prime-power bases. This capability intentionally answers one precise prime query rather than returning the complete prime factorization of n!, which keeps the response small when a caller already knows the prime of interest.
It is suitable for classroom demonstrations, automated answer checking, contest utilities, and backend validation rules. If a workflow needs several primes, call it once per prime and keep each echoed input with its result.
What you can do with it
Check the highest prime power dividing a factorial
Find the largest exponent a for which p^a divides n! without computing the factorial itself.
Evaluate binomial valuations
Combine three factorial exponents to calculate the exponent of p in a binomial coefficient exactly.
FAQ
What does the exponent mean?
It is the greatest integer a such that p^a divides n! with no remainder.
Why must p be prime?
Legendre's formula in this form computes the valuation for one prime. Composite p values are rejected to prevent a different calculation from being mislabeled.
Does the calculator construct n factorial?
No. It adds successive integer quotients of n divided by powers of p, so it avoids the huge factorial value.
What happens when p is greater than n?
The result is zero because none of the factors from 1 through n is divisible by p.
How many trailing zeros does the factorial of 100 have?
It has 24. Each trailing zero needs a 2 and a 5, and factorials contain more 2s than 5s, so the count equals the exponent of 5, which Legendre’s formula gives as 24 for 100.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
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)Example request
{
"n": 100,
"p": 5
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.legendre_formula",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_n | 1000000000 |
max_p | 1000000000 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
The result is the p-adic valuation of n!, often written v_p(n!). It is useful for divisibility questions, trailing-zero calculations, binomial coefficients, number-theory lessons, and programming contests.
What Legendre's formula measures
For n = 100 and p = 5, the terms are 20, 4, and 0, so the exponent is 24. This means 5²⁴ divides 100!, while 5²⁵ does not. The definition includes n = 0 and n = 1: both factorials equal 1, so the exponent of every prime is zero. The response echoes the accepted n and p beside the exponent, making saved results unambiguous.
How inputs are validated and calculated
For example, p = 7 succeeds, while p = 9 returns invalid_input because Legendre's single-prime formula must not be presented as a composite-base valuation. The algorithm is deterministic, uses no network or random source, and produces the same integer result in the browser and API. A successful API request costs $0.002; validation errors are returned as errors rather than plausible-looking numeric results.
Integration use cases
Calculate factorial trailing zeros
Use p = 5 to obtain the number of trailing decimal zeros in n!, or apply the result within other prime-power bases.
Technical questions
How much does an API calculation cost?
Each successful API request costs $0.002. The browser calculator uses the same deterministic core logic.