Obsługa "dużych" liczb całkowitych w C#

Question

Jak obsługiwać duże liczby całkowite w C#?

Mam funkcji, które dadzą mi iloczyn dzielników:

private static int GetDivisorProduct(int N, int product) 
    { 
     for (int i = 1; i < N; i++) 
     { 
      if (N % i == 0) 
      { 
       Console.WriteLine(i.ToString()); 
       product *= i; 
      } 
     } 

     return product; 
    } 

Funkcja powołaniem jest GetDivisorProduct(N, 1)

Jeśli wynik jest większy niż 4 cyfry, powinienem uzyskać tylko ostatnie 4 cyfry . (Np. Jeśli podam wartość wejściową 957, moc wyjściowa wynosi 7493 po przycięciu tylko ostatnich czterech wartości: Rzeczywisty wynik to 876467493.).

Inne przykładowe Wejścia: Jeśli dam 10000, wyjście 0.

Klasa BigInteger został usunięty z biblioteki C#!

Jak mogę uzyskać cztery ostatnie cyfry?

Answer 1

Jeśli patrzysz tylko na cztery ostatnie cyfry, nie potrzebujesz niczego większego niż liczba całkowita. Rozważ to:

Kiedy pomnożenie dwóch liczb, jeśli jesteś zainteresowany tylko w najmniej znaczących cyfr (czyli ostatnie cztery cyfry), a następnie górnym większość cyfry nie będą miały wpływu o najtańszej cyfr wyniku. .. więc możesz po prostu "wyrzucić" najbardziej znaczące (prawe-strony) cyfry zanim pomnożysz.

Na przykład: Chcę pomnożyć dwie duże liczby, ale tylko potrzebne dwie ostatnie cyfry:

int num1 = 123456789; 
int num2 = 987654321; 

int result = num1 * num2; // Last two digits would be "69" but this OVERFLOWS 

ale jeśli pomnożyć tylko dwie ostatnie cyfry ...

int result = (num1 % 100) * (num2 % 100); // result = 89 * 21 

89 * 21 = 1869 (ostatnie dwie cyfry są nadal "" ale nie przelało).

Użyłem tej techniki do obliczenia Six Right-Most Digits of 1,000,000 factorial.

Enjoy,

Robert C. Cartaino

Answer 2

Co powiesz na próbę użycia podwójnego lub długiego zamiast int dla produktu? To działałoby tylko w niektórych przypadkach, ale pozwoliłoby ci pracować z większymi liczbami, które byłeś w stanie.

Answer 3

http://www.codeproject.com/csharp/BigInteger.asp

Answer 4

.NET 4.0 ma BigInteger klasa

Answer 5

Mam nadzieję, że nie missunderstood, ale chcesz pisać w konsoli "0000", jeśli wynik jest 0? Czy próbowałeś:

Console.WriteLine(i.ToString().PadLeft(4,"0")); 

?

Jeśli chcesz uzyskać numer 0000 jako int, przepraszam, ale nie wiem, jak to uzyskać.

Answer 6

Cóż, można zmodyfikować kod tak:

for (int i = 1; i < N; i++) 
    { 
     if (N % i == 0) 
     { 
      Console.WriteLine(i.ToString()); 
      product *= i; 
     } 
     if (product > 10000 * N) 
     { 
      product %= 10000; 
     } 
    } 

To dlatego, że ostatnie cztery cyfry (10000 * K + L) R są takie same jak dla L R. rzeczywistego typu produktu zależy od zakresu N, które chcesz obsłużyć. Jeśli jest to typ całkowity, to produkt powinien być długi.

Nawiasem mówiąc, dlaczego przekazujesz produkt jako parametr, jeśli zawsze jest 1?

Answer 7

Jeśli nie możesz udać się do .NET 4.0 teraz, można użyć BigInteger z J # biblioteki z C#. Here's an article describing how. Ma wpływ na wdrażanie, ponieważ trzeba wdrożyć J# re-distributable.