Primzahlen überprüfen



  • Hallo,
    ich muss auf der Uni eine Funktion implementieren die Primzahlen überprpüft, um mit ihnen dann eine Primfaktorenzerlegung zu machen. So weit so gut aber meine Funktion erkennt z.B. 20 auch als Primzahl und ich verstehe nicht warum. Kann mit eventuell jemand von euch helfen?
    LG

    bool is_prime(int const a) {
    	bool prime(false);
    	for (int i(2); i <= a/2; i++) {
    		if (a%i == 0) {
    			prime = false;
    		}
    		else {
    			prime = true;
    		}
    	}
    	if (a == 2) {
    		prime = true;
    	}
    	return prime;
    }
    


  • Also, wenn ich ich deine Funktion mit 20 ausführe, kommt bei mir raus, dass es keine Primzahl ist. Aber mal abgesehen davon, hast du ein grundsätzlichen Fehler gemacht.
    Deine Funktion entscheidet nach dem folgendem Kriterium:
    Wenn a % a/2 != 0 ist, ist es eine Primzahl. Sprich es wird entschieden, ob es eine Primzahl ist anhand des letzen Durchgangs in deiner for schleife.

    Eine Primzahl ist dann eine Primzahl, wenn sie nur durch sich selbst teilbar ist oder durch 1. Sobald man die zu prüfende Zahl ohne Rest durch eine andere Zahl teilen kann, ist es keine Primzahl mehr. Daher musst du deine Suche abbrechnen, sobald du das erste mal zu dem Ergebnis kommst, dass es sich um keine Primzahl handelt (z.B. durch ein break in deiner for schleife).

    Noch als Tipp: Es ist sinnvoll prime default mäßig auf true zu setzen ... dann sparst du dir den else teil in der for schleife und auch die if abfrage am Ende (Wenn a == 2 ist wird die for schleife direkt übersprungen und prime bleibt logischerweise true)

    Noch zu deiner for schleife, schreib sie so:
    for(int i = 2; i <= a/2; ++i)
    Das initalisieren mit = ist bei integern mehr verbreitet (auch bei bool oben ... bei allen primitiven Datentypen) und ++i ist schneller als i++ (auch wenn der Unterschied gering ist)



    • Wie kommst du auf die Abbruchbedingung i <= a/2; - also warum gerade a/2? Denk mal darüber nach, ob es nicht einen besseren Wert geben könnte.
    • Du weist prime wieder und wieder einen Wert zu. Wenn du einen Teiler findest, wird pime = false gesetzt, aber wenn du danach noch einen nicht-Teiler findest, wird prime auf true gesetzt. Das ist verkehrt. Sobald du irgendeinen Teiler gefunden hast, solltest du die Schleife abbrechen, denn du weißt dann ja, dass es keine Primzahl ist und solltest nicht weiter testen.
    • ich würde davon abraten, int i(2) zu schreiben, wo es synonym zum leichter lesbaren int i = 2 ist. Wenn schon Klammern, dann würde ich geschwungene nehmen, aber wie gesagt, mit =-Zeichen finde ich es leichter lesbar.
    • Du kannst mehrere return-Statements in einer Funktion haben. Damit könnte dein Code ggf. einfacher werden.


  • Hm, wenn ich das hier: https://godbolt.org/z/NwfrmI zum Beispiel für 20 fest eingecoded durchoptimieren lasse, bekomme ich das richtige Ergebnis.
    Wie hast du dass denn im ganzen Code versucht?

    Edit: Eigentlich wollte ich das bei cpp.sh einstellen, aber das will grade nicht.



  • @Leon0402 sagte in Primzahlen überprüfen:

    und ++i ist schneller als i++ (auch wenn der Unterschied gering ist)

    Wie kommst du darauf? Wie hast du das gemessen?
    Bedenke, dass i hier ein int ist und kein komplizierter Objekt-Typ.

    Es wird zumindest auf den gängigen Compilern wie gcc7 identischer Code produziert, der Unterschied ist also nicht nur gering, sondern sogar 0. Sogar bei -O0.



  • @wob sagte in Primzahlen überprüfen:

    Wie kommst du darauf? Wie hast du das gemessen?
    Bedenke, dass i hier ein int ist und kein komplizierter Objekt-Typ.
    Es wird zumindest auf den gängigen Compilern wie gcc7 identischer Code produziert, der Unterschied ist also nicht nur gering, sondern sogar 0. Sogar bei -O0.

    Das war wohl in der Schnelle nicht korrekt. Bei primitiven Datentypen macht es keinen Unterschied, sollte der Compiler in den gleichen Code übersetzen. Bei anderen Sachen kommt es auf die Implementierung an. Postfix kreiert in der Regel eine Kopie und ruft intern den Prefix auf. Die Kopie kann mittlerweile (soweit ich weiß) weg optimiert werden mit RVO. Generell hatte ich mal gelernt:
    "Use ++i if you don't have a specific reason to use i++"
    Im Zweifelsfall die bessere Variante, in dem Beispiel macht es wie du gesagt hast, keinen Unterschied.



  • Danke für eure Antworten meine Funktion sieht jetzt so aus und fuktioniert einwandfrei 🙂

    bool is_prime(int const a) {
    	bool prime(true);
    	for (int i(2); i <= a/2; i++) {										//the square root of a would also be possible
    		if (a % i == 0) {
    			prime = false;
    			break;
    		}
    	}
    	if (a == 2) {
    		prime = true;
    	}
    	else if (a == 3) {
    		prime = true;
    	}
    	return prime;
    }
    


  • @liesl sagte in Primzahlen überprüfen:

    und fuktioniert einwandfrei

    Nope. 0 und 1 sind nicht prim.

    Gegenvorschlag:

    bool is_prime(unsigned a)
    {
    	if (a < 2)
    		return false;
    
    	if (a == 2 || a == 3)
    		return true;
    
    	for (unsigned i = 2; i * i <= a; ++i)
    		if (a % i == 0)
    			return false;
    
    	return true;
    }


  • bool is_prime(unsigned a) {
      if (a < 2) {
        return false;
      }
    
      /*if (a == 2 || a == 3)
        return true;*/
    
      for (unsigned i = 2; i * i <= a; ++i) {
        if (a % i == 0) {
          return false;
        }
      }
      return true;
    }
    

    Alternativ müsste es so auch gehen, da bei a == 2 oder a ==3 die for schleife direkt übersprungen wird und true zurückgegeben wird.

    Nur was deinen Stil angeht, musst du selbst entscheiden. z.B. if mit einer Zeile mit oder ohne Klammern oder ob du es mit einem bool machst oder direkt mit return.
    Ich denke da gibt es unterschiedliche Meinungen zu.



  • Insbesondere sind negative Zahlen nicht als Primzahlen erlaubt.

    #include <iostream>
    
    bool is_prime(int const a) {
        bool prime(true);
        for (int i(2); i <= a/2; i++) {                                     //the square root of a would also be possible
            if (a % i == 0) {
                prime = false;
                break;
            }
        }
        if (a == 2) {
            prime = true;
        }
        else if (a == 3) {
            prime = true;
        }
        return prime;
    }
    
    int main () {
        for (int i = -255; i < 255; ++i) {
            std::cout << i << " is prime " << is_prime(i) << std::endl;
        }
    }
    
    

    Einfach mal die Ausgabe anschauen.



  • @Swordfish Aber im Kontext stimmts. Es geht um Zahlenfaktorisieren und es werden erst zahlen ab 2 kontrolliert ob sie Primzahlen sind



  • Viele Vorschläge, aber bei keinem wird auf Geradheit überprüft und die Zählvariable (von 3 an) um jeweils 2 erhöht. Außerdem steht die Endbedingung vorher fest und muss nicht in jedem Durchgang berechnet werden.



  • @yahendrik
    Ab 4 muss man nicht mehr auf Vielfache von 3 überprüfen. Oder allgemeiner, man muss die Primzahlen vorher überprüfen.
    Da geht sicherlich noch einiges, ist aber die Frage was hier der Anspruch ist.
    Die Endbedingung vorher zu berechnen, ist aber mit Sicherheit eine gute Idee.



  • Ich ging nicht davon aus, daß es bei dieser Frage um Performance geht (und tu das noch immer nicht). Dann müsste man sich von der Methode der Probedivision sowieso verabschieden und ECPP oder AKS nehmen ... oder ausreichend viel Speicher und eine binäre Suche. Reicht ein probabilistischer Primzahltest gehts noch schneller.