"sieb des eratosthenes" - finde meinen fehler nicht

Seite 1 von 2 - Forum: Coding Stuff auf overclockers.at

URL: https://www.overclockers.at/coding-stuff/quotsieb_des_eratosthenesquot_finde_meinen_fehler__154847/page_1 - zur Vollversion wechseln!

also, wir müssen dieses semester prog. in c++ lernen.
dazu gehören immer übungsaufgaben.

dieses mal diese hier.

mein problem liegt bei aufgabe 2.
mein code sieht jetzt so aus:

Code:

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

int size,calc;

int main(void)
{

	printf("Ich moechte die Primzahlen bis zu diesem Wert berechnen:\n");
	scanf("%d",&size);
	
	// Bool'sches Array wird definiert
	bool prim[size];
	
	// Alle Elemente des Arrays werden auf "true" gesetzt
	for (int i=0; i < size; i++)
	{
		prim[i] = true;
	}
	
	// Das erste Element wird auf "false" geÀndert
	prim[0] = false;


	// Sieben
	for (int i=1; i < size; i++)
	{	
		if (prim[i] == true)
		{
			for (int j = 2; j < size; j++)
			{
				calc = i*j;
				prim[calc] = false;
				if (calc > size)
					break;
			}
		}
	}


	// Ausgabe
	for (int k=0; k < size; k++)
	{
		if (prim[k] == true)
		{
			printf("%d \n",k);
		}
	}
	return 0;
}

Im ersten Durchlauf der äußeren Schleife(i immer 1) setzt du in der inneren Schleife ja jedes Feld im Array auf False...
(1x2 -> 2; 1x3 -> 3; 1x4 -> 4;...)

Zumindest was ich rauslesen konnte, bin bisl im Streß

also ich erklär nochmal kurz dazu:
(beispiel: berechnung bis 1000)

er nimmt sich jetzt als erstes das element prim[1], das ist die 2.
die ist als true initialisiert worden, also geht er über in die if-schleife und sofort in die innere for-schleife.
dort wird die 2 jetzt zunächst mit der 2 multipliziert. das ergibt 4. nun wird das feld prim[4] auf false gesetzt. 4 liegt unter 1000, also geht die for-schleife ein weiteres mal durch.
diesmal wird unsere 2 vom anfang mit der 3 multipliziert. das ergibt 6, also wird prim[6] auf false gesetzt. 6 ist kleiner als 1000, also läuft die for-schleife nochmal durch, usw. das geht jedes mal so lange, bis calc die 1000 erreicht hat. dann wird die innere for-schleife unterbrochen.
jetzt kommt als nächstes die 3 dran (denn die steht noch auf "true") und wird zunächst mit der 2 multipliziert. dann mit der 3, dann mit der 4, usw bis calc wieder die 1000 erreicht hat. dann kommt die 4, usw, bis 1000.

ich check nicht, was da verkehrt sein sollte...

Code:

for (int i=1; i < size; i++)
	{	
		if (prim[i] == true)
		{
			for (int j = 2; j < size; j++)
			{
				calc = i*j;
				prim[calc] = false;
				if (calc > size)
					break;
			}
		}
	}

alles klar, problem erkannt.

wenn ich jetzt mal folgendes einfüge:

Code:

for (int i=1; i < size; i++)
	{	
		if (prim[i] == true)
		{
                        [color=red][b]i++;[/b][/color]
			for (int j = 2; j < size; j++)
			{
				calc = i*j;
				prim[calc] = false;
				if (calc > size)
					break;
			}
		}
	}

Code: PHP

for (int i = 2; i < size; i++)
	{	
		if (prim[i] == true)
		{
			for (int j = 2i; j < size; j+i)
			{
				prim[j] = false;
			}
		}
	}

nur so als anregung:
wenn ich auf die zelle prime[calc] zugreifen will sollt ich vieleicht VORHER überprüfen ob calc ein zulässiger wert is

ecraft: funktioniert nicht

smashIt: macht sinn, ja

Code:

        for (int i=1; i < size; i++)
        {
                if (prim[i] == true)
                {
                        i++;
                        for (int j = 1; j < size; j++)
                        {
                                calc = i*j;
                                if (calc < size)
                                {
                                        prim[calc] = false;
                                }
                                else
                                        break;
                        }
                }
        }

Wenn dich dein Prof. ned zerfetzen soll, dann löse es nicht mit einem i++ in einer for(i=x;i<y;i++)-Schleife.

najo, stimmt schon, ist vielleicht etwas unschön.
aber das hier:

Code:

    for (int i=1; i < size; i++)
        {
                if (prim[i] == true)
                {
                        [color=red]int m = i + 1;[/color]
                        for (int j = 1; j < size; j++)
                        {
                                calc = m*j;
                                if (calc < size)
                                {
                                        prim[calc] = false;
                                }
                                else
                                        break;
                        }
                }
        }

Zitat von Gex

if-schleife

Zitat von Tex

warum sagt "jeder" programmieranfänger if-schleife? was bitte hat das mit einer schleife zu tun?

kanns grad nicht testen, aber das sollt hinhaun:

Code: PHP

for(int i=2;i<size;i++){
 if(prim[i]==true){
  for(int j=2;j*i<size;j++){
   prim[i*j]=false;
  }
 }
}

Code: PHP

for (int i = 1; i < prim.Length; i++) 
            {
                if (prim[i] == true)
                {
                    int j = 2*(i+1);
                    while (j < prim.Length)
                    {
                        prim[j-1] = false;
                        j = j + (i + 1);

                    }
                }
            }

@smashIt: funktioniert! vielen dank!

@ecraft: würde evtl auch funktionieren, aber die lösung von smashIt erscheint mir doch simpler. vielen dank trotzdem!

overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025