Fakultät berechnen

[negaH]

@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]