Wie kann ich in einem C Programm prüfen, ob eine Zahl eine Primzahl ist?

5 Antworten

#include <math.h>
#include <stdbool.h>

bool is_prime(int n){
    if(n == 2) return true;
    if(!(n & 1)) return false;
    int z = (int)sqrt(n);
    for(int i = 3; i <= z; ++i) if(!(n % i)) return false;
    return true;
}
Von Experte guenterhalt bestätigt

In pseudocode. 1 Bedeutet Primzahl.

function(x): 
  for(int n; n <= x/2; n++):
    if(x % n != 0):
      return 0
  return 1

Oh, du solltest n bei 2 initialisieren.

1
@guenterhalt

Naja, aber sollte ja trotzdem erkennbar sein wie man das implementiert.

0
@jort93

sollte man nicht davon ausgehen, dass der Fragende oder andere Leser das sofort erkennen?

0
@guenterhalt

Ne, finde ich nicht. Du fängst schleifen ja in 95% der Fälle bei 1 oder 0 an. Wann fängt man schonmal bei 2 an?

0
@jort93

erst einmal ging es darum, der Variablen n überhaupt einen Wert zuzuweisen.

if (x % n != 0)

würde mit n=0 zur Laufzeit unglücklich enden, das sollte man dann gleich merken.
Mit n = 1 ist dann jede Zahl keine Primzahl.
Auch als ungeübter c-Programmierer wird man das schnell erkennen.

Wer so eine Aufgabe nicht durchdenkt, wird sich nicht mal fragen, warum läuft die Schleife nur bis n/2, das % versteht er dann auch nicht.

Ich fand die Zeilen mit Pseudocode schon ganz gut. Das Prinzip ist genannt, die Hausaufgabe (oder so) aber nicht gemacht.

0

muss nur noch in richtigen Code umgewandelt werden. Hätte ich auch so gemacht.

0

und nicht bis n/2 sondern bis sqrt (n). Außerdem sollte man zuerst die 2 und dann nur noch alle ungerade testen

0
@sarah3

Ja, das wäre wohl noch effizienter.

Die Frage ist ob Effizienz gefordert ist. Denn klingt für mich nach einer Programmieraufgabe.

0
@jort93

Trotzdem ist auch da Nachdenken gefragt...

0

Du schaust, ob die Zahl durch eine natürliche Zahl (eigentlich eine Primzahl) bis zur Wurzel aus der Zahl teilbar ist. Wenn nicht, ist es eine Primzahl.

okay, danke... kannnst du mir eventuell bei der Umsetzung helfen?... LG

0

Wenn man vorher prüft ob sie gerade ist, reichen auch alle ungeraden Zahlen bis zur Wurzel.

0

Teile n der Reihe nach von 2 bis n-1 durch alle Zahlen und schaue jeweils, ob ein Rest (d.h. eine Zahl ungleich 0) bei der Division entsteht. Wenn das immer der Fall ist, dann handelt es sich um eine Primzahl.

okay, danke für die hilfe.... die umsetzung muss erstmal gelingen.. erscheint mir gerade nicht so ersichtlich

0
@seidkleiber

ALGORITHMUS istPrimzahl:

Übergabe: n # natürliche Zahl

prim = True

k = 2

SOLANGE k < n:

WENN n % k == 0:

prim = False

k = k+1

Rückgabe: prim

Besser?

2

Kannst duie Hälfte der Prüfungen weglassen, wenn du erst die Zwei testest und dann nur die ungeraden.

0

Mit einer Schleife.

sagen wir mal du willst dir zahl 50 testen:

dann fängt deine Schleife bei 2 an und dann läuft diese bis 25 durch.

und für jede Zahl tested du die 50, also 50 mod schleifenzahl. Wenn bei einer Zahl kein Rest übrig bleibt ist es keine Primzahl und die Schleife bricht ab.

danke! wäre es mögich in einem Code... bin mir gerade iwie nicht sicher

0

nicht bis 25 sondern bis sqrt (50), 50 ist gerade und damit eh ein schlechtes Beispiel.

0

Was möchtest Du wissen?