Primzahlen berechnen (noob)

volkard

Vielleicht liegt Dir mein optimierter Code besser?

#include <iostream>
using namespace std;

int main()
{
    for(int i1 =3; i1 <=1000; ++i1)//Schleifenvariable lokaler
    {
        for(int i2 = 2; i2 < i1; ++i2)//Schleifenvariable lokaler
        {
            if(i1 % i2 == 0)//Wenn ohne Rest teilbar,
                goto keinePrimzahl;//dann war's keine Primzahl.
        }
        //Wenn alle Teiler geprüft wurden und das if nicht anschlug,
        //dann war's doch eine Primzahl.
//Übrigens, genau jetzt gilt i2==i1
//Jetzt wurde i2 so oft erhöht, bis nichtmehr i2<i1. 
//Daran kann man auch testen, ob die Schleife durchgelaufen ist oder abgebrochen 
//wurde. 
        cout << i1 << " ist eine Primzahl!" << '\n';//'\n' besser als endl
keinePrimzahl:
        ;
    }
    cin.get();//Schlecht. Das sollte die IDE übnernehmen
    return 0;
}

robertko

Hallo. Und danke.

Ja, diesen Code verstehe ich.
Wenn ohne Rest teilbar, dann wird die textausgabe übersprungen.
Alles klar.

Aber was ist mit meinem Code?

Diesen würde ich gern verstehen.

volkard

robertko schrieb:

Hallo. Und danke.

Ja, diesen Code verstehe ich.
Wenn ohne Rest teilbar, dann wird die textausgabe übersprungen.
Alles klar.

Aber was ist mit meinem Code?

Diesen würde ich gern verstehen.

Die Codes sind fast identisch, er hat sich nur ums goto gedrückt. Siehe neuen Kommentar "//Übrigens, genau jetzt gilt i2==i1".

Wegen goto bekäme er nämlich Haue vom Prof oder Lehrer.

ps: Eine bool-Variable wäre noch schöner, um sich ums goto zu drücken. Und wenn das klappt, eine Funktion istPrimzahl(int kandidat) und drin ein passendes return. Das wäre ideal.

DocShoe

Noch schöner fände ich es, die Prüfung in eine Funktion auszulagern.

#include <iostream>
#include <cmath>

bool is_prime( unsigned int Number )
{
   if( (Number % 2) == 0 ) return false;

   unsigned int UpperBound = std::sqrt( static_cast<double>( Number ) ) +1;
   for( unsigned int i = 3; i < UpperBound; i += 2 )
   {
      if( (Number % i) == 0 ) return false;
   }
   return true;
}

int main()
{
   for( unsigned int i = 2; i <= 1000; ++i )
   {
      if( is_prime( i ) ) std::cout << i << " ist eine Primzahl\n";
      else                std::cout << i << " ist keine Primzahl\n"; 
   }
}

Zu deiner eigentlichen Frage:
Die Überprüfung wird benutzt, um zu prüfen, ob die innere for-Schleife ohne Abbruch durchgelaufen ist. Sobald das Schleifenkriterium i2 < i1 nicht mehr erfüllt ist wurde die Schleife komplett ohne break durchlaufen und i1 ist gleich i2 .

Edit:
@Volkard:

Idee nur halb zu Ende gebracht. Ich möchte in Zweierschritten nur die ungeraden Teiler probieren.
Persönliche Präferenz. Ich benutze <= eher selten.

volkard

DocShoe schrieb:

Noch schöner fände ich es, die Prüfung in eine Funktion auszulagern.

#include <iostream>
#include <cmath>

bool is_prime( unsigned int Number )
{
   if( (Number % 2) == 0 ) return false;
   
   unsigned int UpperBound = std::sqrt( Number ) +1;
   for( unsigned int i = 3; i < UpperBound; ++i )
   {
      if( (Number % i) == 0 ) return false;
   }
   return true;
}

int main()
{
   for( unsigned int i = 2; i <= 1000; ++i )
   {
      if( is_prime( i ) ) std::cout << i << " ist eine Primzahl\n";
      else                std::cout << i << " ist keine Primzahl\n"; 
   }
}

Was soll der Vortest gegen %2?
Warum +1 statt <=?
Ich würde statt i<=sqrt(Number) lieber testen auf i*i<=Number.

DocShoe

Vorherigen Post aktualisiert.

robertko

Ok Leute.
Jetzt wirds nur noch komplizierter für mich.
Geht doch bitte auf meinen Code ein anstatt besser uund noch bessere zu Posten.
Warum ist i1 und i2 an dieser Stelle == wenn ich das durch die for-schleife doch unterbunden habe.
Ich will es doch nur verstehen.
Mir zu sagen dass sie gleich sind bringt mir nichts, das sehe ich ja selbst, sonst würde das programm ja garnicht funktionieren.
Aber warum ist das so?

@ volkard

Du schreibst i2 wird so oft erhöht bis nicht mehr i2 < i1 gilt.
Wird generell soweit erhöht?
Dann wäre die abbruchbidingung in der for() schleife ja blödsinn.
Ich habe es mal mit i2 <= i1 probiert und das funktioniert auch.
Das macht für mich allerdings sinn
Aber ich verstehe nicht, warum weiter hochgezählt wird, wenn ich das garnicht will.

DocShoe

robertko schrieb:

Ok Leute.
Jetzt wirds nur noch komplizierter für mich.
Geht doch bitte auf meinen Code ein anstatt besser uund noch bessere zu Posten.
Warum ist i1 und i2 an dieser Stelle == wenn ich das durch die for-schleife doch unterbunden habe.
Ich will es doch nur verstehen.
Mir zu sagen dass sie gleich sind bringt mir nichts, das sehe ich ja selbst, sonst würde das programm ja garnicht funktionieren.
Aber warum ist das so?

Liest du die Antworten überhaupt? Habe ich doch erklärt...

daddy_felix

robertko schrieb:

Warum ist i1 und i2 an dieser Stelle == wenn ich das durch die for-schleife doch unterbunden habe.

Das hast du nicht. Der Schleifenrumpf wird solange durchlaufen, wie i2<i1 ist. Irgendwann wird i2==i1 gelten. Dann schlägt die Abfrage fehl (weil i< nicht mehr kleiner i1 ist) und die Schleife wird verlassen.

Die Schleife kann aber anders verlassen werden: wenn i1%i2 = 0. In dem Fall gilt dann i1 != i2 und die if-Abfrage schlägt fehl.

Debugge doch mal durch den Code, dann siehst du das besser.

robertko

Ohh man, das macht sinn.
Danke

Die for schleifen machen mir momentan noch etwas probleme.
Bin halt noch blutiger Anfänger
Ich danke dir.

Wie debugge ich meinen Code?

Bzw. Was ist das?
Hab hier nur n Buch und arbeite es durch.
Debuggen kenne ich noch garnicht.

SeppJ

robertko schrieb:

Bzw. Was ist das?

Was macht man denn zuerst, wenn man einen Begriff nicht kennt?

robertko

Hehe. Das ich darauf keine Antwort bekomme war mir klar, aber erst nachdem ich den Beitrag geschrieben hab. Also, wenn ich das richtig verstanden hab, dann man beim debuggen dem programm beim arbeiten zusehen.
Ok, kann mir das in etwas vorstellen.
Man hat ja beim compilieren die Möglichkeit zwischen debugmodus und releasemodus zu wechseln.
Ich compiliere im debugmodus, aber sehen kann ich da nichts. Ich erkenne auch keinen Unterschied zwischen debug und releasemodus erkennen.
Kann mit das mal jemand etwas genauer erklären.

Danke

volkard

robertko schrieb:

Hehe. Das ich darauf keine Antwort bekomme war mir klar, aber erst nachdem ich den Beitrag geschrieben hab. Also, wenn ich das richtig verstanden hab, dann man beim debuggen dem programm beim arbeiten zusehen.
Ok, kann mir das in etwas vorstellen.
Man hat ja beim compilieren die Möglichkeit zwischen debugmodus und releasemodus zu wechseln.
Ich compiliere im debugmodus, aber sehen kann ich da nichts. Ich erkenne auch keinen Unterschied zwischen debug und releasemodus erkennen.
Kann mit das mal jemand etwas genauer erklären.

Danke

Falls Du den Microsoftcompiler verwendest, dann geh auf eine interessante Zeile und drücke Strg+F4.
Schupps, biste im Debugger und das Programm stoppt bei dieser Zeile. Dann geh mit der Maus über eine Variable. Du siehst ihren Inhalt. Dann schau im Debug-Menu, was da sio geht. Vor allem "Einzelschritt". Und falls noch nicht offen, mach das Fenster auf, was die auto-Variablen anzeigt.

Ethon

volkard schrieb:

Was soll der Vortest gegen %2?

Macht doch Sinn? Jede zweite Zahl fällt durch den Test durch und man spart sich die sauteure Wurzelberechnung.

SeppJ

Ethon schrieb:

volkard schrieb:

Was soll der Vortest gegen %2?

Macht doch Sinn? Jede zweite Zahl fällt durch den Test durch und man spart sich die sauteure Wurzelberechnung.

Dein Programm schrieb:

2 ist keine Primzahl

Jaaaa, macht Sinn.

volkards Vorschlag, wie man die Grenze stattdessen berechnen sollte, ist schon gut. Nicht nur auf Primzahlen bezogen. Den "Trick" kann man auch sonst sehr oft gebrauchen, wenn es darum geht, Wurzeln zu vermeiden. Die Umkehrung (also das Quadrat) einer Wurzel ist nämlich eine streng monoton steigende Funktion. Das heißt, Ordnung bleibt erhalten, wenn man mit den Quadraten arbeitet, anstatt mit den Wurzeln selbst. Und sehr oft will man bloß wissen, wie ein Wert sich zu einem anderen verhält. Dann greift der Trick.
Das gilt natürlich auch für andere Funktionen mit dieser Eigenschaft, aber bei Wurzeln ist es mir in der Praxis mit Abstand am häufigsten begegnet.

Th69

Aber bei

i*i<=Number

aufpassen, daß man keinen Überlauf bei i kriegt (also bei 32-bit integer nur bis i <= 65535).

HarteWare

EDIT: hat sich geklärt, da ließt jemand schneller als er denkt -.-

Habe mal gehört "goto" soll stilistisch nicht sehr gut sein und bin jetzt gerade von einem anscheinend erfahrenen mitglied darauf gestoßen... Simmt das, oder war das nur einfacher so oder was soll ich für die Zukunft denken?

mf

P.S.: Kann man hier keine Beiträge löschen?

SeppJ

HarteWare schrieb:

Habe mal gehört "goto" soll stilistisch nicht sehr gut sein und bin jetzt gerade von einem anscheinend erfahrenen mitglied darauf gestoßen... Simmt das, oder war das nur einfacher so oder was soll ich für die Zukunft denken?

GOTO macht es einfach, unabsichtlich unleserlichen Code zu schreiben.

Swordfish

...

Ethon

HarteWare schrieb:

EDIT: hat sich geklärt, da ließt jemand schneller als er denkt -.-

Habe mal gehört "goto" soll stilistisch nicht sehr gut sein und bin jetzt gerade von einem anscheinend erfahrenen mitglied darauf gestoßen... Simmt das, oder war das nur einfacher so oder was soll ich für die Zukunft denken?

mf

P.S.: Kann man hier keine Beiträge löschen?

In verschachtelten Schleifen kann goto ganz hübsch eingesetzt werden.