Primfaktorzerlegung

Zahlen in Primfaktoren zerlegen

Um die Primfaktoren einer Zahl zu bestimmen, wird die Zahl solange durch einen Teiler (beginnend mit Teiler = 2) geteilt, solange dabei kein Rest entsteht. Sobald bei der Teilung einer Zahl ein Rest ensteht (z.B. 35 / 2 = 17 + 1 Rest), wird der Teiler solange um 1 erhöht, bis diese Zahl wieder mit 0 Rest teilbar wird.

Hier ein anschauliches Beispiel, wie die Zahl 280 in Primfaktoren zerlegt wird:

Zahl modulo Teiler = neue Zahl Rest
280 % 2 = 140 0
140 % 2 = 70 0
70 % 2 = 35 0
35 % 2 = 17 1
35 % 3 = 11 2
35 % 4 = 8 3
35 % 5 = 7 0
7 % 6 = 1 1
7 % 7 = 1 0

Die Primfaktoren von 280 sind somit 2*2*2*5*7

Jeder Teiler dessen geteilte Zahl keinen Rest ergibt, ist ein gültiger Primfaktor. Ist das Ergebnis einer Teilung = 1 und der Rest = 0, wurde der letzte Primfaktor ermittelt. Der letzte Primfaktor ist auch gleichzeitig eine Primzahl.

Daraus ist der folgende Algorithmus abgeleitet:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Primfaktorzerlegung
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Primfaktorenzerlegung: Geben Sie eine Zahl ein! ");
            int zahl = Convert.ToInt32(Console.ReadLine());

            int teiler = 1;     

            Console.Write(zahl + " = ");

            do      // Führe die Schleife aus, solange der Quotient der geteilten Zahl != 1 und der Rest != 0 ist 
            {
                teiler++;   // Der 1. Teiler = 2

                while (zahl % teiler == 0)  // Der Teiler bleibt gleich, solange kein Rest entsteht
                {
                    zahl = zahl / teiler;
                    Console.Write((teiler) + "*");
                }

            } while ( (zahl/teiler != 1) && (zahl%teiler != 0) );   // Ist der Quotient = 1 und der Rest = 0 beende die Schleife
            
            Console.WriteLine(zahl);    // zahl ist eine Primzahl und der letzte Primfaktor

            Console.ReadLine();
        }
    }
}