Legendre-Formel: Primexponent in n! berechnen
Die Primzahl 5 steckt 24-mal in der Fakultät von 100: 100 geteilt durch 5 ergibt 20, 20 geteilt durch 5 ergibt 4, und 20 plus 4 macht 24. Geben Sie n und eine Primzahl p ein und erhalten Sie diesen Exponenten mit wenigen Divisionen. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Rechenbeispiel
- N
- 100
- Leistung (W)
- 5
- Exponent
- 24
Dieser Rechner liefert mit der Legendre-Formel den exakten Exponenten einer gewählten Primzahl p in der Fakultät von n. Statt die riesige Zahl n! zu bilden, teilt er n wiederholt durch p und addiert die ganzzahligen Quotienten. geschrieben. Sie eignet sich für Teilbarkeitsfragen, Endnullen, Binomialkoeffizienten, Zahlentheorie und Programmierwettbewerbe. Jede Eingabe wird als begrenzte ganze Zahl geprüft; zusätzlich wird vor der Berechnung sichergestellt, dass p prim ist. Eine zusammengesetzte Basis führt daher zu einem klaren Fehler statt zu einem irreführenden Wert.
Was die Legendre-Formel misst
Die Formel zählt die Faktoren p im Produkt 1 × 2 × 3 × … × n. Jedes Vielfache von p liefert einen Faktor, jedes Vielfache von p² einen weiteren und jedes Vielfache von p³ noch einen. Der Exponent ist floor(n/p) + floor(n/p²) + floor(n/p³) + weitere Terme bis null.
Der Rechner erweitert die Fakultät nie. Die Antwort nennt n und p eindeutig mit.
Prüfung und Berechnung der Eingaben
Senden Sie n als nichtnegative ganze Zahl und p als Primzahl ab 2. Danach wird quotient = n wiederholt durch floor(quotient/p) ersetzt und zum Exponenten addiert. Das verhindert einen Potenzüberlauf.
Den Exponenten weiterverwenden
Für den Exponenten von p in C(n, k) ziehen Sie die Ergebnisse für k! und (n-k)! vom Ergebnis für n! ab. p^a teilt n!
genau dann, wenn a den ausgegebenen Wert nicht übersteigt. Dezimale Endnullen entstehen aus Paaren von 2 und 5; daher liefert der Exponent von 5 ihre Anzahl. Die Fähigkeit beantwortet bewusst eine einzelne Primzahlanfrage statt der vollständigen Faktorisierung.
Sie passt zu Unterricht, automatischer Prüfung, Wettbewerben und Backend-Regeln. Für mehrere Primzahlen führen Sie je einen Aufruf aus.
Anwendungsfälle
Höchste Primzahlpotenz einer Fakultät prüfen
Bestimmen Sie das größte a, für das p^a die Zahl n! teilt, ohne die Fakultät zu berechnen.
Binomialbewertungen bestimmen
Kombinieren Sie drei Fakultätsexponenten für den exakten Exponenten in einem Binomialkoeffizienten.
Häufige Fragen
Was bedeutet der Exponent?
Er ist die größte ganze Zahl a, für die p^a die Zahl n! ohne Rest teilt.
Warum muss p prim sein?
Diese Formel bewertet eine einzelne Primzahl; zusammengesetzte Werte werden gegen falsche Bezeichnungen abgelehnt.
Berechnet der Rechner n! selbst?
Nein. Er addiert ganzzahlige Quotienten und vermeidet die riesige Fakultätszahl.
Was geschieht, wenn p größer als n ist?
Das Ergebnis ist null, weil kein Faktor von 1 bis n durch p teilbar ist.
Wie viele Endnullen hat die Fakultät von 100?
Sie hat 24. Jede Endnull braucht eine 2 und eine 5, und Fakultäten enthalten mehr Zweien als Fünfen, deshalb entspricht die Anzahl dem Exponenten von 5, den die Legendre-Formel für 100 mit 24 angibt.
Wie finde ich den Exponenten von p in einem Binomialkoeffizienten?
Berechnen Sie den Exponenten von p in n Fakultät und ziehen Sie die Exponenten in k Fakultät und in (n − k) Fakultät ab. Das Ergebnis ist der Exponent von p im Binomialkoeffizienten n über k.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem 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)Beispiel-Anfrage
{
"n": 100,
"p": 5
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.legendre_formula",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Limits
max_n | 1000000000 |
max_p | 1000000000 |
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Das Ergebnis ist die p-adische Bewertung von n!, meist v_p(n!)
Was die Legendre-Formel misst
Für n = 100 und p = 5 ergeben 20, 4 und 0 den Wert 24: 5²⁴ teilt 100!, 5²⁵ nicht. Für n = 0 und n = 1 ist der Exponent null.
Prüfung und Berechnung der Eingaben
Reine Dezimalziffern als Text werden akzeptiert; Brüche, negative Werte, leere Texte, Unendlichkeiten und Grenzüberschreitungen werden abgelehnt. p = 7 ist gültig, p = 9 ergibt invalid_input. Der Algorithmus ist deterministisch, ohne Netzwerk oder Zufall, und liefert in Browser und API dasselbe Ergebnis. Ein erfolgreicher API-Aufruf kostet $0.002.
Integrationsbeispiele
Endnullen einer Fakultät berechnen
Verwenden Sie p = 5 für dezimale Endnullen von n! oder andere Primzahlpotenzbasen.
Technische Fragen
Was kostet eine API-Berechnung?
Jeder erfolgreiche API-Aufruf kostet $0.002. Der Browser nutzt denselben deterministischen Kern.