"sieb des eratosthenes" - finde meinen fehler nicht - Forum

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 14:47

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;
}

er gibt mir nicht alle primzahlen aus, sondern einfach nur eine eins.

ich werd noch bekloppt - wo zur hölle ist da der fehler??

tia

Bearbeitet von Gex am 20.12.2005, 18:26

T3XT4

Beißer

Registered: Jan 2003
Location: .
Posts: 3794

20.12.2005 - 14:56

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ß

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 15:20

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...

Bearbeitet von Gex am 20.12.2005, 15:24

T3XT4

Beißer

Registered: Jan 2003
Location: .
Posts: 3794

20.12.2005 - 15:27

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;
			}
		}
	}

wir gehen in die erste Schleife: i = 1
gehen ins if, weil prim[1] = true
wir gehen in die innere Schleife (i ist noch immer 1, j = 2)

calc wird 2 (weil i=1 und j=2 ... 1*2)
prim[2] = false;

nächster durchlauf der inneren:
calc wird 3 (i noch immer 1, j=3 .. 1*3)
prim[3] = false;

nächster durchlauf der inneren:
calc wird 4 (i = 1, j=4)
prim[4] = false;

...

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 15:50

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;
			}
		}
	}

dann wird i in der if-schleife um 1 erhöht und ist bei der ersten berechnung schon 2. damit wäre das problem der multiplikation mit 1 umgangen.

nun tut das programm aber nichts mehr. ich gebe meinen wert 1000 ein, bestätige, und nichts passiert - ich muss das programm mit strg-c abschießen.

edit: bis zu size 80 läuft das programm durch, gibt aber schwachsinnige werte aus...

:confused:

Bearbeitet von Gex am 20.12.2005, 16:09

Ecraft

Here to stay

Registered: Mar 2002
Location:
Posts: 1096

20.12.2005 - 16:10

Code: PHP

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

ist zwar irsinning dirty aber müsste funktionieren

smashIt

master of disaster

Registered: Feb 2004
Location: OÖ
Posts: 5305

20.12.2005 - 16:20

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

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 16:26

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;
                        }
                }
        }

so gibt er mir jetzt alle ungeraden zahlen aus.
und ich finde den fehler wieder nicht

T3XT4

Beißer

Registered: Jan 2003
Location: .
Posts: 3794

20.12.2005 - 16:31

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

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 16:33

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;
                        }
                }
        }

ändert am ergebnis auch nix...

Tex

got r00t?

Registered: Aug 2000
Location: salzburg
Posts: 1844

20.12.2005 - 16:34

Zitat von Gex
if-schleife

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

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 16:35

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

von mir aus auch if-anweisung oder sonstwas. tut hier aber jetzt relativ wenig zur sache

smashIt

master of disaster

Registered: Feb 2004
Location: OÖ
Posts: 5305

20.12.2005 - 16:50

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;
  }
 }
}

Bearbeitet von smashIt am 20.12.2005, 16:57

Ecraft

Here to stay

Registered: Mar 2002
Location:
Posts: 1096

20.12.2005 - 16:51

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);

                    }
                }
            }

diesmal hab ichs auch getestet

[edit] c# code... (also prim.Length nach size)

Bearbeitet von Ecraft am 20.12.2005, 16:57

Gex

Oralapostel

Registered: Jan 2001
Location: Piefkinesien
Posts: 3376

20.12.2005 - 17:04

@smashIt: funktioniert! vielen dank!

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

Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 14:47 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 = ij; 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; } er gibt mir nicht alle primzahlen aus, sondern einfach nur eine eins. ich werd noch bekloppt - wo zur hölle ist da der fehler?? tia Bearbeitet von Gex am 20.12.2005, 18:26*
T3XT4 Beißer Registered: Jan 2003 Location: . Posts: 3794	20.12.2005 - 14:56 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ß
Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 15:20 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... Bearbeitet von Gex am 20.12.2005, 15:24
T3XT4 Beißer Registered: Jan 2003 Location: . Posts: 3794	20.12.2005 - 15:27 Code: `for (int i=1; i < size; i++) { if (prim[i] == true) { for (int j = 2; j < size; j++) { calc = ij; prim[calc] = false; if (calc > size) break; } } }` wir gehen in die erste Schleife: i = 1 gehen ins if, weil prim[1] = true wir gehen in die innere Schleife (i ist noch immer 1, j = 2) calc wird 2 (weil i=1 und j=2 ... 12) prim[2] = false; nächster durchlauf der inneren: calc wird 3 (i noch immer 1, j=3 .. 1*3) prim[3] = false; nächster durchlauf der inneren: calc wird 4 (i = 1, j=4) prim[4] = false; ...
Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 15:50 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 = ij; prim[calc] = false; if (calc > size) break; } } }` dann wird i in der if-schleife um 1 erhöht und ist bei der ersten berechnung schon 2. damit wäre das problem der multiplikation mit 1 umgangen. nun tut das programm aber nichts mehr. ich gebe meinen wert 1000 ein, bestätige, und nichts passiert - ich muss das programm mit strg-c abschießen. edit: bis zu size 80 läuft das programm durch, gibt aber schwachsinnige werte aus... Bearbeitet von Gex am 20.12.2005, 16:09*
Ecraft Here to stay Registered: Mar 2002 Location: Posts: 1096	20.12.2005 - 16:10 Code: PHP `for (int i = 2; i < size; i++) { if (prim[i] == true) { for (int j = 2i; j < size; j+i) { prim[j] = false; } } }` ist zwar irsinning dirty aber müsste funktionieren
smashIt master of disaster Registered: Feb 2004 Location: OÖ Posts: 5305	20.12.2005 - 16:20 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
Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 16:26 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; } } }` so gibt er mir jetzt alle ungeraden zahlen aus. und ich finde den fehler wieder nicht
T3XT4 Beißer Registered: Jan 2003 Location: . Posts: 3794	20.12.2005 - 16:31 Wenn dich dein Prof. ned zerfetzen soll, dann löse es nicht mit einem i++ in einer for(i=x;i<y;i++)-Schleife.
Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 16:33 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; } } }` ändert am ergebnis auch nix...
Tex got r00t? Registered: Aug 2000 Location: salzburg Posts: 1844	20.12.2005 - 16:34 Zitat von Gex if-schleife warum sagt "jeder" programmieranfänger if-schleife? was bitte hat das mit einer schleife zu tun?
Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 16:35 Zitat von Tex warum sagt "jeder" programmieranfänger if-schleife? was bitte hat das mit einer schleife zu tun? von mir aus auch if-anweisung oder sonstwas. tut hier aber jetzt relativ wenig zur sache
smashIt master of disaster Registered: Feb 2004 Location: OÖ Posts: 5305	20.12.2005 - 16:50 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;ji<size;j++){ prim[ij]=false; } } }` Bearbeitet von smashIt am 20.12.2005, 16:57
Ecraft Here to stay Registered: Mar 2002 Location: Posts: 1096	20.12.2005 - 16:51 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); } } }` diesmal hab ichs auch getestet [edit] c# code... (also prim.Length nach size) Bearbeitet von Ecraft am 20.12.2005, 16:57*
Gex Oralapostel Registered: Jan 2001 Location: Piefkinesien Posts: 3376	20.12.2005 - 17:04 @smashIt: funktioniert! vielen dank! @ecraft: würde evtl auch funktionieren, aber die lösung von smashIt erscheint mir doch simpler. vielen dank trotzdem!

"sieb des eratosthenes" - finde meinen fehler nicht

Forum Index > Software > Coding Stuff

Gex

T3XT4

Gex

T3XT4

Gex

Ecraft

smashIt

Gex

T3XT4

Gex

Tex

Gex

smashIt

Ecraft

Gex