Sieb des Eratosthenes -> Segmentation fault

hi,

ich hab mir ein kleines (hoffentlich) C++-standart-konformes Progammchen geschrieben, was Primzahlen mit dem Algorithmus von Eratosthenes sucht (http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes). Läuft auch super:

#include <iostream>
#include <cmath>

using namespace std;

bool isTeilbar (int a, int b)
{
		if (a % b == 0)
				return true;
		else
				return false;
}

struct Zahl {
		int wert;
		bool prim;
};

int main ()
{
		const long int imax = 1000000;
		const long double dmax = imax;

		Zahl Zahlen[imax]; // Initalisiert imax  Objekte

		for (int i = 2; i < imax; i++)
		{
				Zahlen[i].wert = i;
				Zahlen[i].prim = true;
		}

		// Durchzaehlen und alle Objekte auf true stellen

		for (int j = 2; j <= floor(sqrt (dmax)); j++) // Wiederhole von 2 bis zur Wurzel von dmax
		{
				for (int k = 2 * j; k <= imax; k += j) // Wiederhole vom 2fachen von j bis zu imax;
													   // Gehe in j schritten vor
				{
						Zahlen[k].prim = false;			// Zahl erwischt -> Keine Primzahl
				}

		}

		// Vorlesen

		for (int l = 2; l <= imax; l++)
		{
				if (Zahlen[l].prim)
						cout << Zahlen[l].wert << endl;
		}

		return 0;
}

Toll Rechnet (zählt durch) schneller als Bash erlaubt. Aber wenn ich jetzt an imax noch eine Null dranhänge. Dann bekomm ich einen

Segmentation fault

Was mach ich denn jetzt? Nicht das ich so große Primzahlen brauche. Ich frag nur aus Interesse.

Danke jetzt schom mal!

mfG

Joachim

die Funktion "isTeilbar" gehört nicht zu dem Programm. Sie ist aus versehen mit dazu gekommen. Wäre man ejtzt mal angemeldet

Hallo,

also ich weiß nicht, ob es jetzt der Fehler ist, aber hier mal eine kleine Überschlagsrechnung zum Speicherbedarf:

Die Struct Zahl besitzt ein int (vermutlich 4 Byte groß) und mit dem bool wird es vermutlich auf mind. 8 Byte aufgerundet vom Compiler.
(So du keine Compilerswitches geändert hast, kann man einstellen, das align)
Manchmal rundet er sogar auf 16 Byte auf

Das nimmst du nun 10000000 mal:
(10000000 x 16)/1024^2 ≈ 1,5 GB

Keine Ahnung, wie gut Linux damit klarkommt bzw. wieviel Heap du hast.

PS:

Zahl Zahlen[imax]; // Initalisiert imax  Objekte

Hier wird nix initialisiert.
Nur der Speicher wird reserviert. Welchen Wert die Felder haben, ist nicht geklärt.

for (int k = 2 * j; k <= imax; k += j)                                                       
{
    Zahlen[k].prim = false;
}

In dieser Schleife kann k == imax sein! Dein Array hat aber nur eine Größe von imax, sprich Du greifst über das Array hinaus auf Speicher zu! In der nächsten Schleife dasselbe.

HTH

Info-Student schrieb:

for (int k = 2 * j; k <= imax; k += j)                                                       
{
    Zahlen[k].prim = false;
}
In dieser Schleife kann k == imax sein! Dein Array hat aber nur eine Größe von imax, sprich Du greifst über das Array hinaus auf Speicher zu! In der nächsten Schleife dasselbe.

HTH

Ja stimmt. Hab ich geändert.

SeppSchrot schrieb:

PS:
Zahl Zahlen[imax]; // Initalisiert imax  Objekte
Hier wird nix initialisiert.
Nur der Speicher wird reserviert. Welchen Wert die Felder haben, ist nicht geklärt.

Ja stimmt

SeppSchrot schrieb:

Hallo,

also ich weiß nicht, ob es jetzt der Fehler ist, aber hier mal eine kleine Überschlagsrechnung zum Speicherbedarf:

Die Struct Zahl besitzt ein int (vermutlich 4 Byte groß) und mit dem bool wird es vermutlich auf mind. 8 Byte aufgerundet vom Compiler.
(So du keine Compilerswitches geändert hast, kann man einstellen, das align)
Manchmal rundet er sogar auf 16 Byte auf

Das nimmst du nun 10000000 mal:
(10000000 x 16)/1024^2 ≈ 1,5 GB

Keine Ahnung, wie gut Linux damit klarkommt bzw. wieviel Heap du hast.

Leuchtet ein. Ich könnte aus dem struct ein Array of bool machen. Würde das was bringen? Was kann ich noch verbessern?

rüdiger

1,5GB sind kein Problem auf einer 32Bit Architektur werden an die 4GB (Linux kann sogar durch Tricks noch mehr) unterstützt. Das einzige Problem was du hast, dass der Stack sehr limitiert ist (nur ein paar MB). Also solltest du den Heap für allokationen größerer Daten benutzen.

Sprich

Zahl *zahlen=new Zahl[imax];
//...
delete []zahlen;

Da man in C++ es aber ungern sieht, wenn man Speichermanagement oder ähnliches manuell tätigen muss (wegen Exception Sicherheit und Unzuverlässigkeit von Programmierern), solltest du vielleicht einen Container aus der Standard Library benutzen, am besten würde sich hier wohl std::vector anbieten, was ein (auf dem Heap verwaltetes) dynamisches Array darstellt.

Sprich

#include <vector>
//...
std::vector<Zahl> zahlen;
zahlen.resize(imax);

(Wenn du auch boost benutzt oder dein Compiler TR1 kann, sollte das array Template interessant für dich sein)

btw. imax sollte lieber vom Typ std::size_t sein, anstelle vom Typ int.

nman

Segmentation fault schrieb:

ich hab mir ein kleines (hoffentlich) C++-stan****-konformes Progammchen geschrieben

Dann bist Du wohl im C++-Forum besser aufgehoben.

C++ Forumbot

Dieser Thread wurde von Moderator/in nman aus dem Forum Linux/Unix in das Forum C++ verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Panke

Ich rate dir zu einer Liste und anstatt ein Struct mit Wert/Bool zu nehmen, lösch einfach alle Nicht-Primzahlen aus der Liste.

#include "stdafx.h"
#include <iostream>
#include<fstream>
#include <iomanip>
#include <string>
#include <cmath>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{
        const int limit=10000;
	int prim[limit]={}, n;
	cout<<"bis zu welche zahl willst du die primzahlen berechnen lassen max. "<<limit<<" !!!"<<endl;
	cin>>n;
	if (n>limit)
		cout<<"unzuleassig!!!!"<<endl;
	else
	{
		for (int i=2;i<=n;i++)
		{	
			if (prim[i]==0)
			{
				for (int j=i;j<=n;j=j+i)
				{
					prim[j]=2;
				}
				prim[i]=1;
			}
		}
		for (int i=0;i<=n;i++)
		{
			if(prim[i]==1)
			{
				cout<<setw(5)<<i;

			}
		}cout<<endl;
	}
}

Skym0sh0

was soll das denn jetzt?
dass du hier threads von vorm krieg wieder ausgräbst?!?

vor allem ohne eine aussage deinerseits

SeppJ

Skym0sh0 schrieb:

was soll das denn jetzt?
dass du hier threads von vorm krieg wieder ausgräbst?!?

vor allem ohne eine aussage deinerseits

So etwas kommt vor. Das nennt man einen Troll. Er will durch das Fehlverhalten weitere Antworten provozieren. Dagegen gibt es ein einfaches Mittel: [/close]

Sieb des Eratosthenes -&gt; Segmentation fault

Sieb des Eratosthenes -> Segmentation fault