Feedback

C# - Größter gemeinsamer Teiler

Veröffentlicht von am 22.12.2015
(0 Bewertungen)
Diese Funktion ermittelt den größten gemeinsamen Teiler mehrerer Zahlen. Dabei wird die Primfaktorzerlegung genutzt. Dafür wird eine angepasste Version von diesem Snippet: http://dotnet-snippets.de/snippet/primzahlenermittlung-primfaktorzerlegung/1725 genutzt.
GFU-Schulungen  [Anzeige]

XML und .NET Überblick

Um auf dem neuesten Wissensstand zu sein, sollten Sie unser aktuelles ASP .NET Komplett Seminar belegen.
Nach dem Seminar kennen Sie die wichtigsten Strömungen in der Software-Technologie

Visual Studio Team Foundation Server 2017/2015 (TFS) für Projektmitglieder - Kompakt

Nach Teilnahme an dieser Schulung sind Ihnen die Grundlagen von ALM geläufig. Sie planen und steuern Projekte effizient mit dem Visual Studio Team Foundation Server.

public static int GetGreatestCommenDivisor(IEnumerable<int> source)
        {
            Dictionary<int, int> primes = new Dictionary<int, int>();
            bool firstRun = true;
            foreach (int i in source)
            {
                if (firstRun)
                {
                    firstRun = false;
                    primes = PrimeFactorization(i);
                }
                else
                {
                    Dictionary<int, int> temp = PrimeFactorization(i);
                    foreach (var item in temp)
                    {
                        if (primes.ContainsKey(item.Key))
                        {
                            if (primes[item.Key] > item.Value)
                            {
                                primes[item.Key] = item.Value;
                            }
                        }

                        for (int j = 0; j != primes.Count; j++)
                        {
                            int key = primes.Keys.ElementAt(j);
                            if (!temp.ContainsKey(key))
                            {
                                primes[key] = 0;
                            }
                        }
                    }
                }
            }

            int maxDivisor = 1;
            foreach (var item in primes)
            {
                maxDivisor *= Convert.ToInt32(Math.Pow(item.Key, item.Value));
            }
            return maxDivisor;
        }

public static Dictionary<int, int> PrimeFactorization(int a)
        {
            Dictionary<int, int> primes = new Dictionary<int, int>();
            for (int b = 2; a > 1; b++)
                if (a % b == 0)
                {
                    int x = 0;
                    while (a % b == 0)
                    {
                        a /= b;
                        x++;
                    }
                    primes.Add(b, x);
                }
            return primes;
        }
Abgelegt unter Primfaktorzerlegung, .

Kommentare zum Snippet

 

Logge dich ein, um hier zu kommentieren!