3. Primzahlen-Finder mit Sieb des Erathostenes

Primzahlen-Finder mit Sieb des Erathostenes

  • _

    Hallo,
    ich muss fürs Studium nachfolgende Aufgabe lösen, meine Lösung klappt allerdings nicht. Kann mir jemand sagen, was ich falsch mache bzw. wo mein Denkfehler liegt?

    *Aufgabe:
    Bestimmen Sie Primzahlen zwischen 1 und max = 100 mit dem Sieb des Erathostenes. Hinter diesem Algorithmus steckt das Prinzip, anfangs alle natürlichen Zahlen größer eins zu den Primzahlen zu zählen; im Verlauf des Algorithmus werden die irrtümlich angenommenen (Nicht-)Primzahlen dann heraus gesiebt.

    Schreiben Sie in der Datei gr1.c ein Programm, in dem Sie das folgende Strukturprogramm umsetzen:
    - Feld mit max = 100 Elementen deklarieren
    - Elemente 2 bis max des Feldes mit 1 initialisieren
    - für z = 2 bis z < max
    - Feld[z] = 1 ? JA oder NEIN

    - Wenn JA:
    - Ausgabe der Primzahl z
    - für i = alle Vielfachen (<max) von z
    - Feld[i] = 0*

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

int main()
{
	// Variablen-Deklaration:
	int Feld[100];
	int max, i, y, z;

	// Wertezuweisung max und initialisieren von y:
	max = 100;
	y = 0;

	// 1 keine Primzahl
	Feld[0] = 0;

	// Werte der Felder 2 bis max initialisieren:
	for(z = 2; z <= max; z++)
	{
		Feld[z-1] = 1; // z-1, da Feld-Nummerierung bei 0 beginnt
	}

    for(z = 2; z < max; z++)
	{
		for(i = 2; i < max && y <= max; i++)
		{
            if(Feld[z-1] == 1)
			{
				y = z * i;
				Feld[y-1]=0;
			}
        }
	}

	printf("Primzahlen sind:\n");

	for(z=2; z<=100; z++)
	{
		if (Feld[z] == 1) printf("%i, ",z);
	}

	system("pause");

	return (0);
}
    0
  • H

    moinmoin,

    bis zum initialisieren ist soweit alles gut, ein kleiner fehler ist auf jeden fall schon mal in der Ausgabe. in jedem element des feldes steht immer der wert [index+1]. Deine forschleife läuft von 2 bis 100, Feld[100] gibt es aber gar nicht.

    for(z=0; z<100; z++)               //für alle werte des arrays
    {
        if (Feld[z] == 1) printf("%i, ",z+1);  // gib ggf. den wert, den das 
                                               // element repräsentiert, aus
    }

    die vielfachen einer zahl kann man mit while ganz gut markieren,

    i=???
while (i<max){
  Feld[???]=0      // markieren des entsprechenden eintrages
  i=i+ ???         // hinzuaddieren einer zahl, um das nächste vielfache zu Finden.
}

    das mußt du jetzt nur noch mit geeigneten Indices versehen und in eine schleife packen, damit für jede Zahl die vielfachen gesucht werden. Viel Spaß 😉

    0
  • _

    Vielen Dank für den Tip, hab mir schon Kerben in den Kopf gekratzt vom vielen Grübeln 🙂

    0
  • H

    die indexverschiebung sorgt dafür, dass man sich gut verfriemeln kann. ich habs soweit hinbekommen, aber ich dacht mir, ich lass Dir auch noch ein wenig freude dran.

    kleiner tip, theoretisch brauchst Du die vielfachen eines wertes erst ab dem wert zum quadrat zu markieren.
    die vielfachen von 5, da kannst Du mit 25 anfangen, denn
    15 ist primzahl
    2*5 , 3*5, 4    5 sind schon durch 2,3 und 4 rausgefiltert worden.
    demnach muß man auch nur die vielfachen von 2,3,5,7 rausfiltern, um die primzahlen bis 100 zu finden, denn bei der nächsten primzahl kommst Du ja schon über 100 als startwert (11*11=121)
    das nur so als kleine mathematische spielerei und optimierung am rande.

    0
  • Z

    Ich würde die schleife auf jeden fall umdrehen.
    Ebenso muss die äussere schleife nur von 1 .. sqrt(max) laufen.

    for(z = 1; z < 11; z++) {
        if(Feld[z-1] == 1) {
           for(i = 2; i < max; i++) {
                y = z * i;
                if ( y < max )
                   Feld[y-1]=0;
            }
        }
    }

    Kurt

    edit: Etwas zu spät.

    0
  • _

    Danke nochmal für Eure Tips! 🙂
    Damit auch andere was von diesem Thread haben, hier meine Endfassung, die ich mit Eurer Hilfe nun erarbeitet habe:
    Grüße
    Micha

    //Aufgabe:
//Bestimmen Sie Primzahlen zwischen 1 und max = 100
//mit dem Sieb des Erathostenes. Hinter diesem Algorithmus
//steckt das Prinzip, anfangs alle natürlichen Zahlen
//größer eins zu den Primzahlen zu zählen; im Verlauf
//des Algorithmus werden die irrtümlich angenommenen
//(Nicht-)Primzahlen dann heraus gesiebt.
//
//Schreiben Sie in der Datei gr1.c ein Programm, in dem Sie das folgende Strukturprogramm umsetzen:
//- Feld mit  max = 100  Elementen deklarieren
//- Elemente 2 bis max des Feldes mit 1 initialisieren
//- für  z = 2  bis  z < max
//  - Feld[z] = 1 ? JA oder NEIN
//  
//  - Wenn JA:
//    - Ausgabe der Primzahl z
//    - für  i = alle Vielfachen (<max) von z
//    - Feld[i] = 0

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

int main()
{
	// Variablen-Deklaration:
	int Feld[100];
	int max, i, x, y, z;

	// Wertezuweisung max und initialisieren von y:
	max = 100;
	y = 0;

	// 1 keine Primzahl
	Feld[0] = 0;

	// Werte der Felder 2 bis max initialisieren:
	for(z = 2; z <= max; z++)
	{
		Feld[z-1] = 1; // Setzt alle Zahlen ausser "1" auf den Wert 1, da alles außer 1 erstmal MÖGLICHE Primzahl ist.
	}

	// Primzahlen herausfinden:
    for(z = 2; z <= max; z++) // 1 keine Primzahl, daher Start bei z=2
	{     
		if(Feld[z-1] == 1) //Prüft nur die Zahlen, die als MÖGLICHE Primzahlen gelten
		{
           for(i = 2; i < max; i++) // Schleife erreichnet die Vielfachen der möglichen Primzahl, da diese nicht Primzahl sind
		   {
                y = z * i;
                if (y <= max) Feld[y-1]=0; // Alle Vielfachen der Primzahl bis 100 werden auf 0 = Nicht-Primzahl gesetzt.
            }
        } 
	}

	// Primzahlen ausgeben:
	printf("Primzahlen von 1 bis 100 sind:\n");

	for(z=1; z<=100; z++)
	{
		if (Feld[z] == 1) printf("%i ",z+1); // Ausgabe aller Primzahlen
	}

	printf("\n"); //sorgt nur für Zeilenumbruch nach der Ausgabe

	system("pause"); // Systempause nach Ausgabe

	return (0);
}
    0
Anmelden zum Antworten