C-Code herausfinden, ob Primzahl ist oder nicht - wie?

Folgendes Problem: ich will einen Coode in C schreiben, der mir sagt, ob die Zahl eine Primzahl ist oder nicht. Dazu will ich eine Zahl „so“ überprüfen: ich gebe ihm die Zahl vor, und er soll mit Mod überprüfen, ob die Zahl einen Rest hat; falls nein, teile ich die nochmal so klein wie es geht

Falls ja, ist diese Zahl eine Primzahl

leider fehlt mir das wissen und Verständnis - sofern ich keinen Denkfehler hatte - wie ich meinen Gedankengang in einen Code überführen kann

wäre sehr dankbar für eine Anleitung mit kurzen erklärschritten

danke!

Answer 1

[kmkcl]

Der ganz klassische Ansatz geht in Pseudocode so:

Zahl = Eingabe
Für test = 2 bis Wurzel(Zahl):
  Wenn Zahl modulo test gleich 0 ist:
    keine Primzahl, Schleife abbrechen
Falls Schleife nie abgebrochen wurde, ist Zahl eine Primzahl

Du testest deine Zahl nacheinander mit dem gesamten Zahlenbereich möglicher Teiler durch. Wenn eine Zahl ein Teiler ist, ist der Modulo = 0 und du weißt, dass es keine Primzahl ist. Du könntest natürlich mit dieser Methode auch alle Primfaktoren bestimmen. Etwas optimieren könne man noch, indem man den Teiler 2 separat testet und dann nur alle ungeraden durchgeht.

Eine andere Möglichkeit ist das bereits angesprochene Sieb des Erastosthenes. Das eignet sich, um Primzahlen eines ganzen Zahlenbereiches zu finden. Dabei erzeugst du ein Array von bool-Werten (bzw. in c int-Werte) in der Größe des Zahlenbereichs (von 0 beginnend) und gehst alle Vielfachen durch und setzt die Felder auf false.

Answer 2

[CarinaSchoppe]

gibt den algorithms: sieb des erastosteles oder so damit kannste checken obs ne primzahl ist laufzeit weiß ich nicht kann aber glaube o(n) oder o(n²) sein
deine idee kannste mit while schleife weil das problem du müsstest theoretisch alle zahlen ausprobieren bis zahl x ob diese eine primzahl ist
mittels while ginge das z.b.
int i = 2 weil 1 ist ja klar dass es geht
while zahl % i != 0 do if i == zahl ? break : i++

Woher ich das weiß: Studium / Ausbildung – info studium

Answer 3

[marsthepro]

Ich hatte mal dieselbe Aufgabe und hab es so gemacht.

Habe eine Funktion gemacht die eine Zahl als eingabeparameter hat.

innerhalb der funktion eine Testzahl (beginnend mit 1). Dann die Testzahl mit der gegebenen Zahl teilen und gucken ob der rest 0 ist (also ob teilbar). Falls ja habe ich eine Zähler-Variable von 0 auf 1 inkrementiert. Dann die Testzahl um 1 erhöhen bis man bei der Zahl angekommen ist die man eingegeben hat.

if teiler ==2

return 0; (also wahr)

else

return 1;