Programm verursacht eine Fehlermeldung aus, hat jmd. eine Idee,warum? !!GELÖST!!



  • Untenstehendes Programm soll Primzahlen berechnen und auf der Konsole ausgeben.
    Allerdings wird nach Ausgabe auf der Konsole eine Fehlermeldung (Windowsmeldung "Programm funktioniert nicht richtig") ausgegeben, bei größeren Zahlen(>=10^4) erfolgt sofort die Fehlermeldung ein Programmabbruch. Hat jemand eine Idee, woran das liegen könnte?
    Edit: Der Fehler bestand darin, daß auf Elemente ausserhalb des Index zugegriffen wurde. Code wurde korrigiert.
    (Zeile 27-34 wurden neu eingefügt).

    #include <iostream>
    #include <vector>
    #include <cmath>
    using namespace std;
    
    int main()
    {
      unsigned long long int n;
      unsigned long long int z=0;
      unsigned long long int y;
      cout<<"Bitte geben sie die Zahl ein, "<<endl;
      cout<<"bis zu der Primzahlen berechnet werden sollen: "<<endl;
      cin>> n;
      y=sqrt(n);                                      //Da Primzahlen nur bis zur Wurzel von n berechnet werden müssen
    
      vector<bool> vb(n);                             //Ein Array mit boolschen Werten, Nichtprimzahlen werden markiert.
    
      for(unsigned long long int i = 2; i<=y; ++i)
      {
       if(vb[i]==false)                               //Falls ein Wert auf true steht, also schon als Nichtprimzahl markiert 
                                                      //wurde,geht die Schleife ein Element weiter.
        {
         for(unsigned long long int k=1;(i*k)<=n;++k)
          {
            unsigned long long int m;
            m=(i*(i+k));                          //Produkte der Zahlen 2<=i,k<=m und i*k=m
            if(m<n)                            //Korrektur Beginn
             {
              vb[m]=true;       
             }
            if(i*i<n)
             {
              vb[i*i]=true;
             }                                //Korrektur Ende
    
             //vb[m]=true;                         //!!! fehlerhafter Code!!
             //vb[i*i]=true;             
          }
        }
    
      }
    
      for(unsigned long long int j=2;j<vb.size();j++)      //Ausgabe der Primzahlen
       {
         if(vb[j]==false)
          {
           cout<<" "<<j;
           z+=1;
          }
       }
    cout<<endl<<"Anzahl der Primzahlen: "<<z<<endl;
    return 0;
    }
    


  • for(unsigned long long int k=1;(i*k)<=n;++k) 
    { 
      unsigned long long int m; 
      m=(i*(i+k));                          //Produkte der Zahlen 2<=i,k<=m und i*k=m 
      vb[m]=true;                           //Da das Produkt keine Primzahl ist, wird es markiert 
      vb[i*i]=true;             
    }
    

    Mit der Schleife überschreitest du ziemlich sicher das Ende des vector<>s - und dann schreibst du in Datenbereiche, die dich nichts angehen (und die möglicherweise vom Heap-Managment verwendet werden).

    PS: Zehntausend ist noch keine "größere Zahl" 😃



  • Stimmt, ich habe mal aus

    vb[m]=true;                          
    vb[i*i]=true;
    

    [/code]

    if(m<=n)
    {
     vb[m]=true;       
    }
    if(i*i<=n)
    {
     vb[i*i]=true;
    }
    

    gemacht und schon funktioniert es. Danke für den Tip!

    PS: Zehntausend ist noch keine "größere Zahl" 😃

    Wenn ich mir anschaue, was mein Chef monatlich so überweist....ist 10^4 verdammt groß.
    Wir können uns ja mal anschauen, was Dir Dein Chef monatlich überweist....bestimmt überdenkst Du dann Deine Ansicht noch mal .... 😃



  • redrew99 schrieb:

    Stimmt, ich habe mal aus [...] [...] gemacht und schon funktioniert es. Danke für den Tip!

    Nächster Tip: setz deine Schleifengrenzen gleich so, daß du diese zusätzlichen Überprüfungen nicht benötigst.
    (btw, es reicht auch, i*i einmal als zusammengesetzte Zahl zu markieren ;))

    Edit: Und ehe ich es vergesse: Welches ist der höchste zulässige Index in einem vector mit n Elementen?

    PS: Zehntausend ist noch keine "größere Zahl" 😃

    Wenn ich mir anschaue, was mir mein Chef monatlich überweist....ist 10^4 verdammt groß.
    Wir können uns ja mal anschauen, was Dir Dein Chef monatlich überweist....bestimmt überdenkst Du dann Deine Ansicht noch mal .... 😃

    Wir reden hier auch nicht vom durchschnittlichen SW-Entwickler-Gehalt 😃 Dein Computer bis ca. 18 Trilliarden rechnen (auch wenn das eventuell etwas länger dauert und deinen RAM an die Grenzen bringt), da sind zehntausend wirklich nur eine Kleinigkeit.



  • Merke gerade, daß ich mich zu früh gefreut habe. Nun gibt die Konsole die gleiche Fehlermeldung teilweise doch wieder aus, z.B. bei 10^6 oder mehr, allerdings nicht immer.

    Was genau meinst du mit

    es reicht auch i*i einmal als zusammengesetzte Zahl zu markieren

    ?
    i*i wird doch nur einmal markiert, dadurch,daß sich i verändert (Schleife darüber).



  • Liegt vermutlich an der Frage, die ich dazu-editiert habe.

    redrew99 schrieb:

    Was genau meinst du mit

    es reicht auch i*i einmal als zusammengesetzte Zahl zu markieren

    ?
    i*i wird doch nur einmal markiert, dadurch,daß sich i verändert (Schleife darüber).

    Die innere Schleife hat mehr als einen Durchlauf - und dazwischen ändert sich i (und i*i) nicht.

    Mein Ansatz (sicher noch optimierungswürdig):

    for(i=2;i<y;++i)
      for(k=i;(i*k)<n;++k)
        vb[i*k]=true;
    


  • CStoll schrieb:

    Liegt vermutlich an der Frage, die ich dazu-editiert habe.
    i*i wird doch nur einmal markiert, dadurch,daß sich i verändert (Schleife darüber).Die innere Schleife hat mehr als einen Durchlauf - und dazwischen ändert sich i (und i*i) nicht.

    Stimmt. Einfachste Lösung wäre wohl,

    vb[i*i]=true
    

    im Anschluß an die K-Schleife zu setzen. Aber der Algorithmus ist eh noch lange nicht perfekt, hatte den Code auch nur gepostet wegen der Fehlermeldung.

    Welches ist der höchste zulässige Index in einem vector mit n Elementen?

    n-1,es müßte also heissen

    if(m<=(n-1))
    

    und

    if((i*i)<=(n-1))
    

    Edit:
    Habe n-1 jeweils ergänzt, Code läuft jetzt fehlerfrei 🙂 (Hätte nicht gedacht, daß so oft auf ein Element,welches ausserhalb des Vektors liegt, zugegriffen wird.)

    Jetzt kann ich den Algorithmus weiter optimieren. 🙂
    Freue mich schon auf die nächsten Geschwindigkeitssteigerungen...10^9 in unter 20s gilt es zu erreichen... 😮



  • vb[i*i] mußt du gar nicht gesondert setzen, das wirst du schon innerhalb der Schleife erwischen (k läuft von 1 (ist eigentlich auch nicht ganz richtig) bis n/i, also gibt es auch einen Schleifendurchlauf, in dem k==i gilt).

    redrew99 schrieb:

    Welches ist der höchste zulässige Index in einem vector mit n Elementen?

    n-1,es müßte also heissen

    if(m<=(n-1))
    

    und

    if((i*i)<=(n-1))
    

    Richtig - und meistens schreibt man (weil's kürzer ist ;)) dort dann if(m<n) .


Log in to reply