@salamahachy:
die Anzahl der Nullen kannst du komplett ohne Beechnung der Fakultät ausrechnen.
Schau dir mal obige Expansion von 100! ganz genau an. Wichtig dabei sind alle Primzahlexponenten zur Basis 2 und Basis 5 denn nur diese können mit 2*5 = 0 im Resulat sein.
Vereinfacht für die Basis 10 also so:
Delphi-Quellcode:
function FactorialTrailingZerosBase10(N: Int64): Int64;
begin
Result := 0;
while N >= 5 do
begin
N := N div 5;
Inc(Result, N);
end;
end;
und komplizierter, dafür aber universeller, für alle Basen zwischen 2 bis 48 dann so:
Delphi-Quellcode:
function FactorialTrailingZeros(
const N: Int64; Base: Cardinal): Int64;
// compute count of trailing zeros to base of factorial N!
const
Primes:
array[0..2]
of Cardinal = (2,3,5);
HighestPrime = 7;
HighestBase = HighestPrime * HighestPrime -1;
function PrimePower(N: Int64; Prime: Cardinal): Int64;
begin
Result := 0;
while N >= Prime
do
begin
N := N
div Prime;
Inc(Result, N);
end;
end;
var
I,Multiple: Cardinal;
Power: Int64;
begin
if (Base < 2)
or (Base > HighestBase)
then
raise Exception.CreateFmt('
FactorialTrailingZeros(), Base must be between 2 upto %d', [HighestBase]);
if (N < 0)
then
raise Exception.Create('
FactorialTrailingZeros(), N must be >= 0');
Result := $FFFFFFFF;
for I := Low(Primes)
to High(Primes)
do
begin
Multiple := 0;
while Base
mod Primes[I] = 0
do
begin
Base := Base
div Primes[I];
Inc(Multiple);
end;
if Multiple > 0
then
begin
Power := PrimePower(N, Primes[I])
div Multiple;
if Result > Power
then Result := Power;
end;
if Base = 1
then Exit;
end;
Power := PrimePower(N, Base);
if Result > Power
then Result := Power;
end;
Beispiel:
100! == 2^97*3^48*5^24*7^16*11^9*13^7*17^5*19^5*23^4*29^3* 31^3
*37^2*41^2*43^2*47^2*53^1*59^1*61^1*67^1*71^1*73^1 *79^1*83^1*89^1*97^1
Wir möchten nun wissen wieviele Nullen zur Basis 10 am Ende stehen würden. Die Basis 10 zerlegt sich in 2*5. Also müssen wir obige Exponenten zu den Basen 2 und 5 berechnen. Also 2^97 und 5^24. Nur 2*5 kann eine 0 ergeben, logisch da 2*5 = 10 ergo zur Basis 10 == 0. Das bedeutet wir suchen den kleinsten gemeinsammen Exponnenten von 2^97 und 5^24 und das ist 24 da sie einmal in 24 und 4 mal in 97 reinpasst. Ergo 100! hat exakt 24 Nullen am Ende wenn wir das als Dezimalzahl darstellen wollen.
Angenommmen wir möchten nun wissen wieviele Nullen 100! zu Basis 9 hat. 9 == 3 * 3 == 3^2. Hier haben wir die Basis 3 zum Exponenten 2. Wir berechnen wieder den Primzahlexponeten von 3 in 100! wie oben gezeigt 3^48. Da wir aber die Basis 3 eben 2 mal haben -> 3^2 müssen wir den Exponenten 48 aus 3^48 durch 2 teilen. Ergibt 24, also 24 Nullen enthält 100! am Ende wenn wir 100! im 9'er Zahlensystem darstellen.
Im Zahlensystem 27 -> 3^3 müssenwir also 48 aus 3^48 durch 3 teilen ergibt dann 16 Nullen in 100! im Zahlensystem 27.
Obige Funktion FactorialTrailingZeros() zerlegt nun die Basis "Base" in ihre Primzahlexponentation, zb. 36==2^2*3^2 und berechnet dann jeweils zur Basis 2 und 3 den Exponenten aus der Fakultät von N.
Wir müssen also garnicht N! komplett ausrechnen um die Anzahl der endenden Nullen zu berechnen.
Gruß hagen
[edit]
falls du mein DECMath verwendest nutzt du nachfolgende Funktion. Sie kann mit Basen bis 2^32-1 rechnen.
Delphi-Quellcode:
function NFactorialTrailingZeros(
const N: Int64; Base: Cardinal): Int64;
// compute count of trailing zeros to base of factorial N!
function PrimePower(N: Int64; Prime: Cardinal): Int64;
begin
Result := 0;
while N >= Prime
do
begin
N := N
div Prime;
Inc(Result, N);
end;
end;
var
I,Multiple,Prime,BaseRoot: Cardinal;
Power: Int64;
begin
if Base < 2
then
raise Exception.Create('
NFactorialTrailingZeros(), Base must be >= 2');
if (N < 0)
then
raise Exception.Create('
NFactorialTrailingZeros(), N must be >= 0');
InitSmallPrimes;
Result := $FFFFFFFF;
BaseRoot := Trunc(Sqrt(Base));
I := 0;
repeat
Prime := SmallPrimes[I];
if Prime > BaseRoot
then Break;
Inc(I);
Multiple := 0;
while Base
mod Prime = 0
do
begin
Base := Base
div Prime;
Inc(Multiple);
end;
if Multiple > 0
then
begin
Power := PrimePower(N, Prime)
div Multiple;
if Result > Power
then Result := Power;
end;
until Base = 1;
if Base > 1
then
begin
Power := PrimePower(N, Base);
if Result > Power
then Result := Power;
end;
end;
[/edit]
[edit=Sharky]Zur Vermeidung eines Scrollbalken habe ich in die Zeile mit der Berechnung von 100! einen Zeilenumbruch eingefügt. Mfg, Sharky[/edit]