Primzahlengenerator

niuniu

Hallo liebe Community,

ich bin recht jung in der Programmierwelt und habe dementsprechend wenig Erfahrung. Ich wollte heute zur Übung ein Primzahlengenerator erstellen, aber der funktioniert aus mir nicht ersichtlichen Gründen nur bis zur Zahl 139.

#include <stdio.h>

int main(void)
{
	int flag, i, j, prim[1000], prim_end = 0;
	prim[0] = 2;
	printf("Sieb des Erastothenes - Primzahlen bis 10000\n2 ");
	for(i = 3; i <= 139; i++)
	{
		flag = 1;
		for(j = 0; j <= prim_end; j++)
		{
			if(i % prim[j] == 0)
				flag = 0;
		}
		if(flag != 0)
		{
			printf("%u ", i);
			prim[prim_end++] = i;
		}
	}
	return 0;
}

Wenn ich in der achten Zeile in der Bedingung der for-schleife die Zahl 139 durch eine größere ersetze, beendet das Programm mit dem Fehler "Sieb des Erastothenes.exe funktioniert nicht mehr". Bei 139 und einer kleineren Zahl liefert mir das Programm wie gewünscht alle Primzahlen bis zur eingegeben Zahl.

Sieb des Erastothenes - Primzahlen bis 10000
2 3 4 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
 107 109 113 127 131 137 139

Ich hoffe ihr könnt mir helfen.

Gruß
niuniu

EDIT: Tut mir Leid, aber ich den Fehler gerade selber gefunden. In Zeile 19 gehört statt ein Postinkrement ein Preinkrement. Die einstündige Fehlersuche hat sich somit erledigt.

wxSkip

Ich habe die Vermutung, dass die Arraygrenzen verletzt werden - finde aber gerade keinen Fehler.

Trotzdem noch 2 Anmerkungen:
1. Zeile 14 könntest du noch {}-klammern und ein break; reinmachen, dann musst du nicht mehr weitersuchen.
2. Das, was du da betreibst, ist nicht das Sieb des Eratosthenes: http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Wutz

Je nachdem, wie groß du den Wert wählst, reicht prim[1000] nicht mehr aus, dein Programm versucht dann, auf nicht definierte Speicherbereiche schreibend zuzugreifen -> Abbruch.
Ebenso greifst du auf undefinierte prim Bereiche zu (Schleife läuft zu weit) und dann kann bei modulo Division durch 0 auftreten -> Abbruch.
Deine prim[0]=2 wird übrigens überschrieben.

SeppJ

In Zeile 19 muss das ++prim_end heißen.

Mit der 139 hat das nichts direkt zu tun, das ist nur Zufall. Denn wenn du es so machst wie bisher, dann wird die alte letzte Zahl überschrieben und danach zeigt prim_end auf ein uninitialisiertes Element von prim. Und wenn da zufällig eine 0 steht, dann hast du eine Division durch 0 und das Programm stürzt ab.

Und ich sehe nicht, wo hier nach Erastothenes gesiebt würde.

niuniu

danke für eure hilfe.
stimmt, es handelt sich nicht um den sieb des erastothenes, aber das ist in meinem fall irrelevant, da ich einfach nur einen primzahlengenerator erstellen wollte.

hier der korrekte code, falls jemand in zukunft ein ähnliches problem haben sollte:

#include <stdio.h>

int main(void)
{
    int flag, i, j, prim[10000], prim_end = 0;
    prim[0] = 2;
    printf("Primzahlen bis 10000\n2 ");
    for(i = 3; i <= 10000; i++)
    {
        flag = 1;
        for(j = 0; j <= prim_end; j++)
        {
            if(i % prim[j] == 0)
			{
                flag = 0;
				break;
			}
        }
        if(flag)
        {
            printf("%u ", i);
            prim[++prim_end] = i;
        }
    }
    return 0;
}