Primzahlen auslesen funktioniert nur bis 100

zpol

Hallo,
Ich muss für meine Uni ein C++-Programm schreiben mit dessen Hilfe man die Primzahlen bis zu einem selbst gewählten Endpunkt berechnen lassen. Das Programm funktioniert soweit auch gut, aber sobald man als Endpunkt Zahlen wählt die größer als 100 sind wird das Programm einfach ohne Ausgabe beendet.

#include <iostream>
using namespace std;
int main(int argc, char** argv){
	int n;
	cout<<"Geben Sie eine Zahl an bis zu der Sie auf Primzahlen testen moechten: "<<endl;
	cin>>n;
	bool isPrime[n];

	int i=2;

for(i=0;i<n;i++){
	isPrime[i]=true;}

for(i=2;i<n;i++)
{

	if(isPrime[i]==true)
	   {
	   int j;
	   int d=0;
	     for(j=2;d<n;j++)
	        {d=j*i;
	         isPrime[d]=false;
	        }
	   }
}

int y;
for(y=0;y<=n;y++)
        {
	if (isPrime[y]==true)
               {
		cout<<y<<", ";
	        }
        }

return 0;
}

Wahrscheinlich ist der Fehler eh ganz offensichtlich und ich bin einfach betriebsblind. Aber falls jemand einen Fahler entdecken sollte wäre das sehr nett mir den aufzuzeigen

daddy_felix

nimm anstelle von bool isPrime[n]; mal nen std::vector.

zpol schrieb:

[...]
	   int d=0;
	     for(j=2;d<n;j++)
	        {d=j*i;
	         isPrime[d]=false;
	        }
[...]

bist Du sicher, dass immer gilt d<n?

Ausserdem: Warnungen im Compiler einschalten! Dein Array variabler Länge ( bool isPrime[n]; ) ist kein C++!

daddy_felix schrieb:

nimm anstelle von bool isPrime[n]; mal nen std::vector.

nimm anstelle von std::vector<bool> einen std::vector<char> (aber speichere trotzdem nur true/false darin)

zpol

@daddy_felix und damn_vector_bool: Der Übungsassistent meinte dass wir unsere Programme nur mit den in der Vorlesung durchgemachten Themengebieten lösen dürfen. std::vector gehört leider nicht dazu...

@furble wurble: Wenn man n nichtnegativ wählt sollte das doch zumindest beim ersten Durchlauf der Fall sein. Die Schleife soll ja eben abgebrochen werden wenn d grösser als n ist. Wieso ist das denn kein C++? Soll ich n auf const setzen?
(Warnungen sind eingeschalten)

Ich habe nun d mit 2*i initialisiert und das Programm funktioniert jetzt bis 140^^.

Aber eigentlich sollte das doch nicht so schnell abbrechen. Was ist denn eigentlich der Grund für den Abbruch wenn ich d mit 0 initialisier. Einfach weil das Programm probiert auf einen sozusagen nicht existenten Teil eines Arrays zuzugreifen? Und wieso passierte das erst bei 100? Und warum jetzt bei 140? Ich bin das ganze Programm im Debug Mode(Eclipse) durchgegangen, verstehe es aber trotzdem nicht...

Ah ja.. Sorry für den Doppelpost.

zpol schrieb:

Der Übungsassistent meinte dass wir unsere Programme nur mit den in der Vorlesung durchgemachten Themengebieten lösen dürfen. std::vector gehört leider nicht dazu...

Okay.
Dann nimmst Du ein starres Array der Größe m und n muss halt kleiner sein. Hier z.B. mit m=1024

bool isPrime[1024];
  int n;
  cout<<"Geben Sie eine Zahl an bis zu der Sie auf Primzahlen testen moechten: "<<endl;
  cin>>n;
  if(1024<n)
    return -1;

Die ganze Arbeit macht ja dieser Teil:

for(i=2;i<n;i++)
{
    if(isPrime[i]==true)
       {
       int j;
       int d=0;
         for(j=2;d<n;j++)
            {
             d=j*i;
             isPrime[d]=false;
            }
       }
}

Warum überhaupt die Variable j?
Wenn Du d richtig initialisierst (2*i), die Laufbedingung d<n setzt und danach mit Schrittlänge i durch das Array marschierst(*) ist doch alles geritzt?
Wikipedia hat den Algorithmus so auch als Pseudocode da stehen.

Das Hauptproblem oben ist, dass die Laufbedingung d<n beim (erneuten) Eintritt in die Schleife ausgewertet wird, du d allerdings im Schleifenkörper zuweist und _dann_ als Index in Dein Array benutzt.

(*) Mit Schrittlänge meine ich den Wert, um den Du d erhöhst, z.B. Schrittlänge vier wäre sowas

for(int i=0; i<42; i+=4) /* blabla */;

SeppJ

damn_vector_bool schrieb:

daddy_felix schrieb:

nimm anstelle von bool isPrime[n]; mal nen std::vector.

nimm anstelle von std::vector<bool> einen std::vector<char> (aber speichere trotzdem nur true/false darin)

Es wurde hier im Forum schon mehrmals festgestellt, dass der vector<bool> für diese Aufgabe günstiger ist. Keiner seiner Nachteile greift bei dieser Aufgabenstellung, dafür ist er schneller und kann bis zu größeren Zahlen benutzt werden.

zpol

Furble Wurble schrieb:

Das Hauptproblem oben ist, dass die Laufbedingung d<n beim (erneuten) Eintritt in die Schleife ausgewertet wird, du d allerdings im Schleifenkörper zuweist und _dann_ als Index in Dein Array benutzt.

Danke dir! Jetzt funktioniert alles wunderbar. Ich frage mich nur noch warum der Programmcode am Anfang bei 140 noch funktionierte und bei 141 nicht mehr. Kann mir das wirklich nicht erklären.

Falls ich den Code hier reinschreiben soll sagt mir das bitte.
Danke nochmal!

zpol schrieb:

Ich frage mich nur noch warum der Programmcode am Anfang bei 140 noch funktionierte und bei 141 nicht mehr. Kann mir das wirklich nicht erklären.

Dass es bei Dir bei 141, oder bei 150 "knallt" ist Zufall - bei anderen mag es früher oder später zu Problemen kommen. Wenn Du über Arraygrenzen schreibst/liest passieren immer wunderliche Dinge.

Manche schwören auf Debugger.
Andere schwören auf logging auf die Konsole - ich auch!

Z.B. könnte eine einfache Verzweigung mit Ausgabe schon Hinweise geben, wenn man den Fehler ungefähr lokalisiert hat.
Im folgenden gibt es zwar eigentlich erst ab d==1023 Probleme, aber es verdeutlicht, wo Dein ursprüngliches Programm über dass Array hinausschrieb.
(Ich habe noch die Deklaration der Laufvariablen in den Schleifenkopf mit reingenommen - macht man so in C++)

#include <iostream>

using namespace std;

int main(int argc, char** argv){
  bool isPrime[1024];
  int n;
  cout<<"Geben Sie eine Zahl an bis zu der Sie auf Primzahlen testen moechten: "<<endl;
  cin>>n;
  if(1024<n)
    return -1;

  for(int i=0;i<n;i++)
  {
    isPrime[i]=true;
  }

  for(int i=2;i<n;i++)
  {

    if(isPrime[i]==true)
    {
      int j;
      int d=0;
      for(j=2;d<n;j++)
      {
        d=j*i;
        if( !(d<n) )
        {
          std::cerr<<"index (would be) out of bounds!(d: " << d << " i: " << i << ")\n";
          if(!(d<1024)) return -1;  // genug ist genug!
        }
        isPrime[d]=false;
      }
    }
  }

  for(int i=0; i<n; ++i)
  {
    if (isPrime[i]==true)
    {      
       cout<<i<<", ";
    }
  }
}