C Sieb des Eratostenes

[Taxotic]

Nabend,
Ich lerne gerade für die bevorstehende Info-Klausur und stoße immer wieder auf Probleme.
Bei den letzten Aufgaben wurde mir hier immer sehr schnell geholfen, dafür bin ich Euch sehr dankbar! Wenn ihr Lust habt, dann werft doch mal ein Blick auf das folgende Problem:

Primzahlen ermitteln: Sieb des Eratostenes

Eine Liste aller Zahlen (bis n) wird angelegt. Alle Zahlen, die das Produkt der Multiplikation
zweier Zahlen zwischen 2 und n sind, werden aus der Liste gestrichen.

Bei meinem Code werden nun immer alle Zahlen ausgegeben, vielleicht liegt das Problem in der Verschachtelung der for-Schleifen?

#include <stdio.h>
#include <stdlib.h> 


int main()
{
	int *liste;
	int i;
	int kprimzahl;
	int anzahl;

	printf("Bis zu welcher Zahl sollen die Primzahlen ausgegeben werden?\n");
	scanf("%i",&anzahl);
	liste= (int *) malloc (anzahl* sizeof(int));	

	//Array füllen:

	for (i=0; i<anzahl; i++)
	{
		liste[i]=i;
	}

	//Berechnung:

	for (i=0; i<anzahl; i++)
	{
		kprimzahl=2*i;							//keine Primzahl ist das Produkt aus 2*i
			for (i=0; i<anzahl; i++)			// Vergleiche alle Einträge der Liste mit "kPrimzahl"
				{
					if (kprimzahl==liste[i])	//Stimmt ein Eintrag überein, so schreibe 0 in die Liste
					liste[i]=0;
				}
			
	}
	
			
	//Ausgabe:
		for (i=0; i<anzahl; i++)		
			{	if (liste[i] != 0)				//Ist der Eintrag !=0, so gebe ihn aus
					{
					printf("%i\n",liste[i]);
					}
			}
	
	return 0;

}

 

[misu]

Also erstmal, du kansnt das array mit überall mit 1 initialisieren (muss nicht mit i sein). Das geht übrigens elegant mit memset().
Als nächstes, du willst prüfen, ob eine Stelle 1 ist, um dann alle vielfachen zu nullen. Weder prüfst du, ob eine stelle eins (oder bei dir i) ist, noch setzt du alle vielfachen korrekt auf 0. Irgendwie machst du das nur für alle Vielfachen von 2 (Zeile 27).

Ergänzung (14. Juli 2012)

Zumindest die Ausgabe sollte passen.

 

[Harzerkas]

Hier stand Unsinn!

 

[maxwell-cs]

genau, einfach einen array anlegen, der für jede zahl angibt, ob sie schon gestrichen ist.

in einer äußeren schleife dann die zahlen 2...n durchgehen. immer, wenn eine noch nicht gestrichene zahl gefunden wird (kleine verständnisübung: warum reichen die noch nicht gestrichenen?), werden in einer inneren schleife alle vielfachen gestrichen.

 

[hackebeil]

fail in zeile 28.
im moment wird die äußere schleife nur einmal ausgeführt, weil die innere i bis anzahl hochzählt. wenn die innere schleife durch ist, ist auch die abbruchbedingung der äußeren erfüllt.

ersetze i durch j an den passenden stellen.

 

[Taxotic]

Nabend,

ich habe auch gerade festgestellt, das meine Berechnung ziemlicher Quatsch ist. Ich setz mich morgen früh nochmal ran, mit etwas mehr Konzentration.

Danke für Hilfe!

Ergänzung (14. Juli 2012)

Hallo,

könnt ihr mir sagen warum er jetzt bei der Berechnung nachdem er die Vielfachen=0 gesetzt hat nicht in die äußere Schleife zurückspringt?

Danke!

#include <stdio.h>
#include <stdlib.h> 


int main()
{
	int *liste;
	int i;
	int j;
	int anzahl;

	printf("Bis zu welcher Zahl sollen die Primzahlen ausgegeben werden?\n");
	scanf("%i",&anzahl);
	liste= (int *) malloc (anzahl* sizeof(int));	

	//Array füllen:

	for (i=0; i<anzahl; i++)
	{
		liste[i]=i;
	}

	//Berechnung:

	for (i=2; i<anzahl; i++)			/
	{
		if (liste[i]!=0)
		{
			j=2*i;
			while(j<anzahl)
					{
					liste[j]=0;
					j=2*j;
					}
		}
	}
			
	//Ausgabe:
		for (i=0; i<anzahl; i++)		
			{	if (liste[i] != 0)				//Ist der Eintrag !=0, so gebe ihn aus
					{
					printf("%i\n",liste[i]);
					}
			}
	
	return 0;

}

 

[Wurstinator]

Wie kommst du darauf, dass er nicht dorthin springt? Bei mir funktioniert das.

Das Problem ist eher, dass deine Berechnung immernoch falsch ist.
Welche Werte nimmt j z.B. dann an, wenn i=7 ist?
j = 14
j = 28
j = 56
j = 112

Die 49, die sich in 7*7 zerlegen lässt, wird nicht gestrichen.



Noch zwei Hinweise, die du vielleicht beachten möchtest:
1. Es gibt keinen Grund dafür, dass liste ein int-Array ist. Jedes Mal, wenn du auf liste zugreifst, gibt es nur zwei Möglichkeiten für diesen Wert: entweder ist er gleich mit i oder er ist 0. Da es nur zwei Zustände gibt, kannst du ein bool-Array verwenden.
2. Null und Eins sind keine Primzahlen

 

[Taxotic]

Ahrr, ich mach auch echt immer doofe Fehler... Danke für den Tipp!

  int main()
    {
    int *liste;
    int i;
    int j;
    int anzahl;
     
	  printf("Bis zu welcher Zahl sollen die Primzahlen ausgegeben werden?\n");
	  scanf("%i",&anzahl);
	  printf("\n\n");
	  liste= (int *) malloc (anzahl* sizeof(int));	
     
    //Array füllen:
     
		 for (i=0; i<anzahl; i++)
			  {
				  liste[i]=i;
			  }
     
    //Berechnung:
     
	 for (i=2; i<anzahl; i++)	//für alle Zahlen
		  {
				 if (liste[i]!=0)		//wenn der Eintrag nicht 0 ist
			  {
							
					for(j=2; j*i<=anzahl;j++)
						 {
							liste[j*i]=0;
						
						 }
			  }
		 }


    //Ausgabe:

    for (i=2; i<anzahl; i++)	
		 {	
		 if (liste[i] != 0)	//Ist der Eintrag !=0, so gebe ihn aus
				 {
				 printf("%i\n",liste[i]);
				 }
		 }
    return 0;
     
    }

 

[Wurstinator]

Mir ist gerade noch aufgefallen: In Zeile 15 und 38 muss ein <= sein.

Funktioniert der Code jetzt so, wie er soll?

 

[Darlis]

Nein, <= wäre ein Fehler, da liste nur anzahl Elemente hat.

 

[Wurstinator]

Stimmt, dann musst du auch noch anzahl+1 Elemente reservieren

 

[Darlis]

Beim jetzigen Code muss er das nicht. i<anzahl ist die gängigere Praxis, dabei sollte er auch bleiben.
In Zeile 27 muss das aber noch korrigiert werden.

 

[TheRed]

Vergiss nicht dein Speicher wieder frei zu geben, sonst gibts Abzug.

 

[Wurstinator]

@ Darlis: Das würde dann aber nicht der Eingabe entsprechen.

 

[Darlis]

Du meinst i<anzahl entspricht nicht der Eingabe, da i nicht bis anzahl hochgezählt wird?
Es werden aber trotzdem anzahl Elemente in der Liste durchlaufen, was logisch korrekt ist. Man muss natürlich bedenken, dass das erste Element in der Liste den Index 0 hat und du mit liste[anzahl] außerhalb liste wärst, was andere Sprachen mit einer Exception beantworten würden.

 

[1668mib]

Speicher freigeben? Was solls, das wird am Ende des Programms ja eh gemacht. Schlimmer ist, dass das Programm quasi wahllos im Speicher schreibt ohne es zu dürfen..

Zeile 29. greift auf Index i*j zu - was deutlich über anzahl liegen kann ... (im Worst-Case ist es ~anzahl²)..

Es ist im Übrigen sinnlos, wenn man im Zahlenbereich bis anzahl nach Primzahlen sucht, den Zähler bis zu diesem Wert hochzuzählen. Es reicht vorher die Wurzel zu berechnen und abzurunden.

Beispiel 10...
was ist überhaupt kleiner gleich 10?
2*2
2*3
2*4
2*5
3*2 <-- ist aber das selbe wie 2*3
3*3
4*2 <-- ist aber das selbe wie 2*4
5*2 <-- ist aber das selbe wie 2*5
Es reicht also bis zur 3 (inklusive) zu zählen in der äußeren Schleife.. und in der inneren reicht es so lange zu zählen, so lange i*j < oder <= anzahl (je nach konkreter Implementierung)...

 

[Darlis]

Zeile 29. greift auf Index i*j zu - was deutlich über anzahl liegen kann ... (im Worst-Case ist es ~anzahl²)..

Das wird in Zeile 27 ja abgefangen. Es wird also höchstens auf liste[anzahl] zugegriffen.

 

[1668mib]

@Darlis: Ups, lustigerweise hab ich echt schlech gelesen ^^ (was auch ein wenig an der etwas durchwachsenen Formatierung liegt *mich raus red*)
hab ja die selbe Abbruchbedigung wie sie da steht hingeschrieben ;-)

Als Startwert wäre in der inneren Schleife aber dennoch i zu empfehlen aufgrund der Symmetrien...

 

[TheRed]

Wo wird den der Speicher freigegeben. Dass macht vllt Windows von sich aus selbst, aber falls du mal woanderst programmierst kann dass zu abstürzen führen. Daher sollte man den
Speicher immer freigeben und gerade bei einer Klausur gibt das sofort Punktabzug.

 

[1668mib]

@TheRed:
Ich sitmm dir zu wenn du mir ein Programm zeigst, das abstürzt, weil es am Ende der main-Funktion den in der main-Funktion allokierten Speicher nicht freigegeben hat, und der Absturz eben dadurch verhindert wird, dass die letzte Anweisung vor dem return-Statement eben "free ..." ist... und bitte ohne irgendwie rekursive Aufrufe der main-Funktion oder ähnlichen Unsinn...

Lustig ist aber, dass Dinge die wirklich zum Absturz führen hier gar nicht gemacht werden,also Prüfen ob der Zeiger überhaupt gültig ist... das würde bei mir Punktabzug geben...
Und wenn mir jemand Punktabzug gibt, weil ich am Ende der main-Funktion dynamischen Speicher nicht manuell freigegeben habe, und es vorher nicht so kommuniziert wurde, dass es vorausgesetzt wird, dann sag ich dem aber meine Meinung.