Wie kann ich in C# die beiden Teiler einer Zahl, die die kleinste Differenz haben, ermitteln?

Ich habe das Problem, dass ich von einer Ganzzahl, die zwei Teiler benötige, welche die geringste Differenz zwischen einander haben.

Bei 30 wären das also 5 & 6, da beide Teiler von 30 sind und eine Differenz von nur 1 haben. Bei 17, was ja eine Primzahl ist, wären es 1 & 17, da es die einzigen beiden Teiler der Zahl sind.

Wie kann ich es in C# umsetzen, dass ich die Zahl eingebe und die beiden Teiler berechnet und in Variablen gespeichert werden?

Answer 1

[regex9]

Das ist in erster Linie ein mathematisches Problem. Du brauchst alle möglichen Teiler, um von diesen dann die gemeinsame Differenz zu ermitteln.

Beispiel:

Zahl: 6

6 : 6 = 1
6 : 3 = 2
6 : 2 = 3
6 : 1 = 6

Es reicht dabei, von 1 bis sqrt(6) (beide Grenzen inklusiv) zu gehen und je Schritt die jeweilige Zahl durch 6 zu teilen. Wenn ein Ergebnis ohne Nachkommastelle (bzw. Rest) herauskommt, hast du einen ganzen Teiler gefunden.

Die Quadratwurzel kannst du in C# mit der Sqrt-Methode berechnen.

int number = (int) Math.Sqrt(6);

Eine Division, bei der der Rest ermittelt wird, lässt sich mit dem Modulo-Operator bewerkstelligen.

int rest1 = 6 % 2; // 0
int rest2 = 6 % 4; // 2 (6 : 4 = 1 mit Rest 2 (6 - 4 * 1))

Um die beider Teiler zu sichern, könntest du dir eine Liste an Tuples anlegen:

IList<Tuple<int, int>> factors = new List<Tuple<int, int>>();
factors.Add(new Tuple<int, int>(2, 3));
factors.Add(new Tuple<int, int>(1, 6));

Console.WriteLine("First number of second entry is " + factors[1].Item1); // 1
Console.WriteLine("Second number of second entry is " + factors[1].Item2); // 6

Dieser Zwischenschritt, sich die Teiler erst zu speichern und später ihre Differenz zu prüfen, ist m.E. allerdings unnötig. Die Differenz könnte man sich stattdessen sofort berechnen und in einer Variable merken, sofern diese nicht schon eine vorher berechnete Differenz beinhaltet, die kleiner ist, als die gerade berechnete.

Answer 2

[daCypher]

Was soll denn passieren, wenn es mehrere Teiler mit dem gleichen Abstand gibt?

Z.B. bei der 30 gibt es die Teiler 1, 2 und 3, die jeweils einen Abstand von 1 haben und dann erst die 5 und die 6, die auch einen Abstand von 1 haben.

Also du musst:

1. Die Primfaktoren der Zahl bestimmen (so, wie regex9 es gesagt hat)
2. Die Abstände zwischen den Primfaktoren bestimmen
3. Den kleinsten Abstand bestimmen
4. Alle Faktoren ausgeben, die den kleinsten Abstand aufweisen (bzw. je nach Aufgabenstellung z.B. nur das erste oder das letzte Faktorenpaar ausgeben)

Comments

[daCypher]

Ich hab mal was gebastelt:

class Program
{
    static void Main()
    {
        while(true)
        {
            Console.WriteLine("Bitte Zahl eingeben");
            string input = Console.ReadLine();
            if (int.TryParse(input, out int number))
            {
                // 1. Primfaktoren ermitteln
                List<int> divisors = Divisors(number);


                // 2. Differenzen zwischen den Primfaktoren ermitteln
                List<int> differences = Differences(divisors);


                // 3. Mindestdifferenz ermitteln
                int min = differences.Min();


                // 4. Indizes mit Mindestdifferenz ermitteln
                IEnumerable<int> indizes = differences.Select((num, index) => new Tuple<int,int>(num, index)).Where(tuple => tuple.Item1==min).Select(tuple => tuple.Item2);


                // 5. Ergebnis ausgeben.
                Console.WriteLine($"Kleinster Abstand: {min}. Faktoren: {string.Join(", ", indizes.Select(i => divisors[i] + "-" + divisors[i+1]))}.");
            }
        }
    }


    static List<int> Divisors(int number)
    {
        List<int> result = new List<int>();
        number = Math.Abs(number); // negative Zahlen umdrehen


        for (int i = 1; i <= number; i++) // Alle Teiler zur Ergebnisliste hinzufügen
        {
            if (number % i == 0) result.Add(i);
        }


        return result;
    }


    static List<int> Differences(List<int> numbers)
    {
        List<int> result = new List<int>();
        for (int i = 1; i < numbers.Count; i++) // Die Abstände der Zahlen berechnen
        {
            result.Add(numbers[i] - numbers[i - 1]);
        }
        return result;
    }
}