Einführung in C#
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(); } } }