Kann man mithilfe der Summenformel nach Gauß berechnen ob eine Zahl eine Primzahl ist?

Erste Frage Aufrufe: 449     Aktiv: 30.11.2020 um 20:07
0

Der Titel sagt eigentlich schon alles, ich weiß es ist vielleicht eine .omische Frage, aber ich habe bis morgen eine informatik Hausaufgabe zu erledigen, in der zweiten Aufgabe sollen wir die Summenformel nach Gauß benutzen, in der letzten Aufgabe sollen wir testen ob eine Zahl eine Primzahl ist, in dem nur eine Zahl angegeben wird. Es gibt dafür auch Wege, allerdings benutzen diese Lösungen einige Dinge die wir noch nicht gelernt haben, deswegen habe ich nachgedacht, und vielleicht kann man eine Verbindung zwischen den beiden Sachen machen.

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
2 Antworten
0

Einen solchen Zusammenhang gibt es meiner Meinung nicht. Man kann prüfen, ob eine Zahl eine Primzahl iost mittels  "Sieb des Erastosthenes". Kennst Du das?

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 6.14K

 

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Professorrs wurde bereits informiert.
0

Die Summe der ersten \(n\) natürlichen Zahlen \(\sum_{i=1}^ni=\frac{n(n+1)}2\) ist nie prim für \(n>2\), denn die Gauß'sche Summenformel gibt ja eine Faktorisierung an. Wenn deine Zahl also genau von dieser Form ist, kannst du sagen, dass sie nicht prim ist.

Ansonsten ist es nicht schwer, einen einfachen (wenn auch ineffizienten) Primzahltest zu programmieren. Um zu testen, ob \(p\) prim ist, prüfe einfach, ob es eine Zahl \(2\leq k\leq\sqrt p\) gibt, die \(p\) teilt.

Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Das muss ich erst einmal verstehen, was ist in diesem Fall k?   ─   cookie 30.11.2020 um 20:06
Du musst über alle natürlichen Zahlen \(k\) zwischen \(2\) und \(\sqrt p\) iterieren (in einer Schleife). Innerhalb der Schleife überprüfst du immer, ob \(k\) deine zu testende Zahl teilt. Ist das für mindestens ein \(k\) so, dann ist \(p\) keine Primzahl. Teilt kein \(k\) deine Zahl, dann ist es eine Primzahl. Wollen wir zum Beispiel prüfen, ob 35 eine Primzahl ist, dann überprüfen wir nacheinander:
Ist 35 durch 2 teilbar? nein.
Ist 35 durch 3 teilbar? nein.
Ist 35 durch 4 teilbar? nein.
Ist 35 durch 5 teilbar? ja. also ist 35 keine Primzahl.   ─   stal 30.11.2020 um 20:07

Kommentar schreiben