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.
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!