Primzahlen berechnen
will man zum Beispiel bei Visual Basic ein Programm schreiben, dass überprüft, ob Zahlen Primzahlen sind, macht man das mit einer Schleife, die von 2 bis zur Wurzel der Zahl geht. Meine Frage ist jetzt, warum man die Schleife nur bis zur Wurzel der Zahl machen muss? Ich habe gelesen, dass es nur Teiler bis zu der Wurzel geben kann aber warum ist das so? Ich habe leider keine der Erklärungen verstanden >.<
Hier nochmal mein Code zur Verständnis:
Dim p As Long = tbPrimzahl.Text
Dim Counter As Long
Dim Primzahl As Boolean = True
For Counter = 2 To Math.Sqrt(p) Step 1
If p Mod Counter = 0 And Counter <> 1 Then
Primzahl = False
MsgBox(p & " ist keine Primzahl.", MsgBoxStyle.OkOnly)
Exit Sub
End If
Next Counter
4 Antworten
Daß es nur Teiler bis zur Wurzel geben kann, stimmt nicht. Aber es genügt, die Teiler bis zur Wurzel zu suchen. Denn wenn eine Zahl bis zur Wurzel keinen Teiler hat, dann kommt auch nach der Wurzel kein Teiler mehr. Den Grund dafür hat freejack75 erklärt: Hätte die Zahl einen Teiler, der größer als die Wurzel ist, dann müßte sie auch einen haben, der kleiner als die Wurzel ist.
Man kann die Teiler der Zahl in Paare teilen:
d1 * d2 = n;
d3 * d4 = n;
...
So sind die Teilpaare in umgekehrten Verhältnis. Wenn d größer ist, als sqrt(n), dann muss seine Paare kleiner als sqrt(n) sein.
wenn eine Zahl aus nur zwei Faktoren z = p *q besteht, dann wäre für p > Wurzel z der zweite Faktor q < Wurzel z, und damit bereits gefunden worden.
Das Argument trifft auch dann zu, wenn p und/oder q wiederum teilbar ist und z damit mehr als zwei Teiler hat.
benutzt doch einfach mal google dailyfreecode.com/code/check-number-prime-not-vb-net-code-3346.aspx