Primzahlen mit der Containerklasse "list" .... Aber wie ?

[Wiesel]

Hi,

kann mir mal jemand sagen wie man folgende Aufgabe löst ?

Aufgabe:

Aus einer Liste mit den Zahlen von 2 bis Obergrenze werden zunächst alle echten Vielfachen von 2 gestrichen, anschließend alle echten Vielfachen von 3, dann die echten Vilefachen von5, die echten Vielfachen von 7 usw. Alle noch in der Liste verbleibenden Zahlen sind dann Primzahlen.

Das Programm soll die Containerklasse "list" (doppelt verkettete Liste) verwenden.

Ich beiß mir dabei die Zähne aus, könnte vielleicht jemand mal den Code posten ?

[Guybrush Threepwood]

Wie wärs wenn du erstmal deinen Ansatz postest und genau sagst womit du Probleme hast?

[Wiesel]

ich bekomm noch nicht mal den ansatz hin.

ich würde mich freuen wenn mir mal jemand die lösung postet um mich dan reinzudenken.....

die aufgabe ist aus son ner liste mit aufgaben leider ohne lösung....

[Goos]

ich bekomm noch nicht mal den ansatz hin.

ich würde mich freuen wenn mir mal jemand die lösung postet um mich dan reinzudenken.....

die aufgabe ist aus son ner liste mit aufgaben leider ohne lösung....

Wenn du noch nichtmal den Ansatz hinkriegst, dann solltest entweder in deiner Liste zur naechsten Aufgabe wechseln, oder ein wenig Grundlagenforschung im Internet betreiben um einen Ansatz entwickeln zu koennen

Eine Aufgabe ist schliesslich auch zum Loesen da und nicht zum "in die Loesung reindenken", wobei letzteres auch in 99% aller Faelle nicht klappt.

Goos

[kLeiner_HobBes]

SPOILER!!! *gg

OK, ich gebs zu, mir war grad langweilig und eigentlich sollte man es selbst machen und so weiter .. aber immerhin ist es im Moment nicht geschwindigkeitsoptimiert!!!

#include <iostream>

#include <list>


using namespace std;


void main()

{

	const OBERGRENZE = 50;


	typedef list<int> intliste;

	typedef list<int>::iterator myiterator;


	intliste primzahlen;


	//Liste füllen

	for (int i=2; i<=OBERGRENZE; i++)

		primzahlen.push_back(i);


	//Nicht-Primzahlen rausschmeißen

	for (myiterator lauf = primzahlen.begin(); lauf != primzahlen.end(); lauf++)

		for (myiterator i = lauf; i != primzahlen.end(); )

		{

			myiterator temp = i++;

			if ((*temp) % (*lauf) == 0 &&  temp != lauf)

				primzahlen.erase(temp);

		}



	//Liste ausgeben

	for (myiterator m = primzahlen.begin(); m != primzahlen.end(); m++)

		cout << (*m) << endl;


	cin.get();


}

[Guybrush Threepwood]

.. aber immerhin ist es im Moment nicht geschwindigkeitsoptimiert!!!

Was ihm bestimmt als erstes aufgefallen ist;)

[Wiesel]

danke für die hilfe, hab es mitlerweile auch hinbekommen, ist eigentlich ähnlich meiner lösung...

dennoch danke wie gesagt, ich werd das ein oder andere noch von dir übernehmen denke ich und was die geschwindigkeit angeht, das ist mir schon aufgefallen, man kann beim löschen noch etwas performanter umgehen...

[Goos]

danke für die hilfe, hab es mitlerweile auch hinbekommen, ist eigentlich ähnlich meiner lösung...

dennoch danke wie gesagt, ich werd das ein oder andere noch von dir übernehmen denke ich und was die geschwindigkeit angeht, das ist mir schon aufgefallen, man kann beim löschen noch etwas performanter umgehen...

Hmm... nix fuer ungut, aber wieso fragst hier ueberhaupt noch nach ner Loesung, wenn du dann schon ein paar Stunden nachdem du nichtmal den Ansatz wusstest schon selbst ne komplette Loesung hast?

Goos

[kLeiner_HobBes]

Der Ansatz ist ansich schon etwas unperformant. Ich würd es eher so machen:

#include <iostream>

#include <list>

#include <math.h>


using namespace std;


bool is_prime(int number)

{

	if (number  < 4) return true;

	if (number % 2 == 0 || number == 0) return false;


	for (int i = 5; i < sqrt(number); i+=2)

		if (number % i == 0) return false;

	return true;

}


void main()

{

	const int OBERGRENZE = 500000;

	typedef list<int> TMyList;

	typedef list<int>::iterator TMyIterator;


	TMyList primzahlen;


	for (int i = 2; i < OBERGRENZE; i++)

		if (is_prime(i))

			primzahlen.push_back(i);


	for (TMyIterator it = primzahlen.begin(); it != primzahlen.end(); it++)

		cout << (*it) << endl;

}

Berechnung hat ca. 1-2 sek. gedauert, während ich die nicht optimierte Lösung von heut Mittag bei gleicher OBERGRENZE nach ein paar Minuten abbrach.