# Sieb des Eratosthenes



## braveheart10 (9. Dezember 2010)

Hi,
so wie mein code unten steht gibt er mir alle Primzahlen bis 5000 aus.
Ich möchte aber das er mir nur die ersten 500 Primzahlen ausgibt - hab schon alles probiert da ne zählschleife einzubaun aber ich bekomms nicht hin.
Hoffe hier kann jemand helfen.
Mfg


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


int pr_feld[5000];  //Array der zu überprüfenden Zahlen
int i;              //Zählvariable
int j;              //Funktionsinterner Zähler
 
main(void)
{  
	//Sieb des Eratosthenes
	for(i=2; i <= (sizeof(pr_feld)/sizeof(int)); i++) 
	{
		if(!pr_feld[i])
		{
			printf("%4d\t",i);
			for(j = 1;(j*i) <= (sizeof(pr_feld)/sizeof(int));++j) 
			{
				pr_feld[(j*i)] = 1;
			}
		}
	}
	system("Pause"); 
}
```


----------



## sheel (9. Dezember 2010)

```
#include <stdio.h>
#include <stdlib.h>
 
 
int pr_feld[5000];  //Array der zu überprüfenden Zahlen
int i;              //Zählvariable
int j;              //Funktionsinterner Zähler
 
int main(void)
{  
	for(i=0;i<5000;i++)pr_feld[i]=0;
	int iii=0;
    //Sieb des Eratosthenes
    for(i=2; i <= 5000; i++) 
    {
        if(!pr_feld[i])
        {
            iii++;
            if(iii>500)break;
            printf("%4d\t",i);
            for(j = 1;(j*i) <= (sizeof(pr_feld)/sizeof(int));++j) 
            {
                pr_feld[(j*i)] = 1;
            }
        }
    }
    system("Pause");
	return 0;
}
```

Nur die drei Zeilen mit iii.
Wenn man ++ und das if zusammenfasst, nur zwei.

Und mach doch nicht solche seltsamen sizeof-Sachen


----------



## kickerxy123 (9. Dezember 2010)

Hallo,
sizeof ist sehr unschön (bei mir lief das Programm z.B. nur bis 1000 ).

ich würde dir folgendes vorschlagen:

```
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define max_prim 500
 
bool pr_feld[(max_prim+1)];  //Array der zu überprüfenden Zahlen

int main(void)
{  
for(int i = 0; i <= max_prim; i++)
{
   pr_feld[i] = false;
}
    //Sieb des Eratosthenes
    for(int i=2; i <= max_prim; i++) 
    {
        if(!pr_feld[i])
        {
            printf("%4d\t",i);
            for(int j = 1;(j*i) <= max_prim;++j) 
            {
               if((j*i) <= max_prim)   
                  pr_feld[(j*i)] = true;
            }
        }
    }
    printf("beliebige Taste zum Beenden druecken...");
    getch();
return EXIT_SUCCESS; 
}
```

noch ein paar Anmerkungen: getch() ist besser als system(), da es nicht manipuliert werden kann und dein Array pr_feld musst du vorher initialisieren (mit false auffüllen). Wenn du das nicht tust, kommt es in (zwar ganz seltenden) Fällen vor, dass ein Element in dem Array zufällig ein true enthält und somit deine Berechnung ein Fehler aufweist!


Gruß
kickerxy


----------



## braveheart10 (9. Dezember 2010)

Ihr seid SUPER!
vielen dank.


----------



## Matthias Reitinger (9. Dezember 2010)

sheel hat gesagt.:


> Und mach doch nicht solche seltsamen sizeof-Sachen


Wieso? Diese „seltsamen sizeof-Sachen“ sind in jedem Fall besser als magische Konstanten, die man im Quelltext verstreut. 



kickerxy123 hat gesagt.:


> sizeof ist sehr unschön (bei mir lief das Programm z.B. nur bis 1000 ).


Dann ist dein Compiler kaputt.



kickerxy123 hat gesagt.:


> ich würde dir folgendes vorschlagen: […]


Damit werden allerdings nicht die ersten 500 Primzahlen ausgegeben, sondern alle Primzahlen bis 501.

Grüße,
Matthias


----------



## kickerxy123 (9. Dezember 2010)

Mag sein, dass es an meinem älteren Dev-Cpp->Mingw Compiler liegt...
mir ist grade nicht ganz klar, warum bei mir bis 501 gegangen werden sollte..?

Ich finde nach wie vor meine #define -Variante schöner als sizeof()- Konstrukte, zumal so oder so an einer Stelle 500 stehen muss. Aber gut, das ist sicher Ansichtssache.


#edit bzgl. 501/500: meinst du wegen "++j" ?  Ist mir grade aufgefallen... das verwende ich eigentlich auch nicht, nur da der Threadstarter dieses so hatte... dann sollte man das in "j++" ändern. Kann mich aber da auch grade nicht mehr reindenken, da ich ziemlich müde bin und jetzt los muss.

#edit2: Nein, meine Schleifen waren trotzdem korrekt... Wenn man 
	
	
	



```
if(!pr_feld[i]
```
 auskommentiert, dann zählt er brav von 2 bis 500.

Gruß und einen schönen Abend
kickerxy


----------



## Matthias Reitinger (9. Dezember 2010)

kickerxy123 hat gesagt.:


> mir ist grade nicht ganz klar, warum bei mir bis 501 gegangen werden sollte..?


Mein Fehler, das müsste natürlich 500 heißen. Der eigentliche Kritikpunkt bleibt trotzdem: gefragt war nach den _ersten 500_ Primzahlen, nicht nach den Primzahlen, die _kleiner oder gleich 500_ sind. Das ist natürlich ein Unterschied. Die ersten 10 Primzahlen sind beispielsweise 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29, während die Primzahlen kleiner gleich 10 nur 2, 3, 5 und 7 sind.

Grüße,
Matthias


----------



## braveheart10 (10. Dezember 2010)

Hatte jetzt nur sheel seine schleife in mein programm eingebaut und dann kickerxy123s code gar nicht mehr compilier aber die anderen haben recht ich suche die ersten 500 Primzahlen (2 bis 3571).

noch ne frage:

liegt das an meinem IDE oder warum bekomm ich beim compilieren nen fehler wenn ich die typdefinition der zählvariable z.B. i  inerhalb der forschleife mache? (funktioniert bei mir nur wenn ich sie erst auserhalb deklariere.
benutze Visual C++ 2008 Express Edition.

geht:
int i;
for(i=2;...

geht nicht:
for(int i=2;...


----------



## sheel (10. Dezember 2010)

Und welcher Fehler kommt?


----------



## deepthroat (10. Dezember 2010)

Hi.





braveheart10 hat gesagt.:


> noch ne frage:
> 
> liegt das an meinem IDE oder warum bekomm ich beim compilieren nen fehler wenn ich die typdefinition der zählvariable z.B. i  inerhalb der forschleife mache? (funktioniert bei mir nur wenn ich sie erst auserhalb deklariere.
> benutze Visual C++ 2008 Express Edition.
> ...


Das ist der Unterschied zwischen C (vor 1999) und C++.

Du kompilierst deinen Code offenbar als C Code. Der Visual C Compiler unterstützt den "neuen" C Standard von 1999 aber nicht und demnach darfst du die Variablen nicht innerhalb der for Anweisung definieren.

Mit dem MSVC ist es eigentlich sinnvoller den C Compiler gar nicht mehr zu benutzen und stattdessen den C++ Compiler als einen _verbesserten_ C Compiler einzusetzen.

Benenne einfach deine Dateien nicht mit .c sondern mit .cpp als Endung.

Gruß


----------



## braveheart10 (10. Dezember 2010)

ahh, genau der fehler danke.

Wie sieht das heute mit der kompatibiltät des Programmes auf anderen Systemen/Plattformen/Microcontrollern aus.
Wenn dort die Programmierung eines C-programms verlangt wird schlucken die dann auch den C-code mit der .cpp endung?


----------



## braveheart10 (10. Dezember 2010)

Hab eben mal Kickerxy123s Programm versucht als .c auszuführen(mit .cpp keine Beanstandung).
Bekomme den o.g. fehler in der for schleife das ist klar - aber er meckert jetzt noch wegem dem array


error C2061: Syntaxfehler: Bezeichner 'pr_feld'
error C2059: Syntaxfehler: ';'
error C3409: Ein leerer Attributblock ist nicht zulässig
error C2143: Syntaxfehler: Es fehlt ']' vor '('
error C2059: Syntaxfehler: 'Konstante'
error C2059: Syntaxfehler: ')'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ')' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2065: 'i': nichtdeklarierter Bezeichner
warning C4552: '<=': Operator hat keine Auswirkungen; Operator mit Nebeneffekt erwartet
error C2065: 'i': nichtdeklarierter Bezeichner
error C2059: Syntaxfehler: ')'
error C2143: Syntaxfehler: Es fehlt ';' vor '{'
C2065: 'pr_feld': nichtdeklarierter Bezeichner
error C2065: 'i': nichtdeklarierter Bezeichner
error C2109: Index erfordert ein Array oder einen Zeigertyp
error C2065: 'false': nichtdeklarierter Bezeichner
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ')' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2065: 'i': nichtdeklarierter Bezeichner
warning C4552: '<=': Operator hat keine Auswirkungen; Operator mit Nebeneffekt erwartet
error C2065: 'i': nichtdeklarierter Bezeichner
error C2059: Syntaxfehler: ')'
error C2143: Syntaxfehler: Es fehlt ';' vor '{'
error C2065: 'pr_feld': nichtdeklarierter Bezeichner
error C2065: 'i': nichtdeklarierter Bezeichner
error C2109: Index erfordert ein Array oder einen Zeigertyperror C2065: 'i': nichtdeklarierter Bezeichner
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ')' vor 'Typ'
error C2143: Syntaxfehler: Es fehlt ';' vor 'Typ'
error C2065: 'j': nichtdeklarierter Bezeichner
error C2065: 'i': nichtdeklarierter Bezeichner
warning C4552: '<=': Operator hat keine Auswirkungen; Operator mit Nebeneffekt erwartet
error C2059: Syntaxfehler: ')'
error C2065: 'j': nichtdeklarierter Bezeichner
error C2143: Syntaxfehler: Es fehlt ';' vor '{'
error C2065: 'j': nichtdeklarierter Bezeichner
error C2065: 'i': nichtdeklarierter Bezeichner
error C2065: 'pr_feld': nichtdeklarierter Bezeichner
error C2065: 'j': nichtdeklarierter Bezeichner
error C2065: 'i': nichtdeklarierter Bezeichner
error C2109: Index erfordert ein Array oder einen Zeigertyp
error C2065: 'true': nichtdeklarierter Bezeichner
========== Erstellen: 0 erfolgreich, Fehler bei 1, 0 aktuell, 0 übersprungen ==========


----------



## kickerxy123 (10. Dezember 2010)

naja.. ich weiß grad nicht, ob es alle Fehler ausräumt, aber C kennt standardmäßig nicht den Typen bool.

du könntest 
	
	
	



```
#ifndef BOOL
typedef int BOOL;
#endif
#ifndef FALSE
#define FALSE 0
#define TRUE 1 
#endif
```
 und dann alle Vorkommnisse von bool/true/false auf BOOL/TRUE/FALSE ändern.

Gruß,
kickerxy


----------



## deepthroat (10. Dezember 2010)

braveheart10 hat gesagt.:


> ahh, genau der fehler danke.
> 
> Wie sieht das heute mit der kompatibiltät des Programmes auf anderen Systemen/Plattformen/Microcontrollern aus.
> Wenn dort die Programmierung eines C-programms verlangt wird schlucken die dann auch den C-code mit der .cpp endung?


Wenn du auf Portabilität Wert legst, solltest du C Code auch in .c Dateien speichern (und dann evtl. auf C99 Spracheigenheiten verzichten).

Allerdings kann man bei eigentlich jedem Compiler explizit einstellen in welcher Sprache eine Quelldatei zu lesen ist.

Bei MSVC kannst du auchfür jede Quelldatei in den Eigenschaften festlegen ob die Datei als C oder C++ Code kompiliert werden soll:




Gruß


----------



## Trulleberg (10. Dezember 2010)

Wenn du dich konsequent an den C89 Sprachstandard hälst, dann bist du maximal portabel, d.h. du kannst mit unter Windows entwickeln und zum Schluss den Releasestand mit deinem MC- C-Compiler fertigstellen. Du wirst dann schon merken (und zwar schon unter Windows), was nicht zum C89 Standard gehört.
Für den gcc unter Windows (=MinGW) wäre dann z.B. die Option -ansi empfehlenswert.
Für MSVC sollte die Datei mit .c enden, du solltest keine "_irgendwas" Funktionen benutzen und keine NICHT-C89-Standard Headers benutzen (z.B. nicht conio.h,windows.h usw.) um C89 konform zu bleiben.


----------



## braveheart10 (11. Dezember 2010)

noch eine letzte frage.

ich möchte mit diesen ersten 500 primzahlen die ich ermittelt habe nun weiter rechnen.
wie kann ich nun auf diese zugreifen?

z.B.
er soll die erste Primzahl (p=2) nehmen rechnen und ausgeben x= (2^p)-1 
danach soll er auf die nächste Primzahl (p=3) zugreifen x errechnen und ausgeben
und so weiter bis zur 500ten Primzahl.


----------



## sheel (11. Dezember 2010)

Entweder musst du die Primzahlen in einem Array zwischenspeichern, oder auch gleich da ausgeben, wo jetzt die Primzahlen ausgegeben werden.

Die Formel, die du angegeben hast, wäre in C-Schreibweise
(1<<p) -1

Aber bist du dir sicher, dass du die Aufgabenstellung richtig verstanden hast?
Du wirst so nämlich mit den normalen Variablen nicht auskommen.

Ein (unsigned) int mit 32bit kommt bis zu Werten von 4294967295 = 2^32 -1
Deine Berechnung würde also nur für die ersten 11 Primzahlen (31 ist die elfte) funktionieren, weil für die höheren das Ergebnis nicht mehr in die Variablen passen würde.
Deine Primzahlen gehen aber bs ca. 3500 statt 31 

Für die höheren Zahlen gibts verschiedene Bibliotheken, die das können...aber hast du nicht doch was falsch verstanden?


----------



## braveheart10 (11. Dezember 2010)

hätte da jetzt die <math.h> eingebunden 
und irgendwas mit double pow versucht.

kannst du mir sagen die du das meinst das alles nochmal in ein array zu speicher?
weil wenn ich die ausgabe in die andere schleife einbaue gibt er mir ja erst die primzahl und dann das x aus - und das 500 mal
ich möchte aber erst die 500 primzahlen und dann die x berechnung.

das ist die aufgabenstellung:
Schreiben Sie ein C++-Programm, das ermittelt, für welche Zahlen z = (2 p ) -1 ( 2 hoch p ) -1 Primzahlen sind, wenn p selbst eine Primzahl ist .
Beispiel Für p = 2 ist 2 2 -1 = 3 eine Primzahl oder für p= 3 ist 2 3 -1 = 7 eine Primzahl,
aber x =2 11 -1 = 2047 ist keine Primzahl

also x soll dann auch nur ausgegeben wenn basis^exponent auch wieder eine Primzahl ist. das werden dann natürlich keine 500 zahlen.


----------



## sheel (11. Dezember 2010)

Wie ich schon geschrieben habe, für diese Aufgabe wirst du eine externe Bibliothek brauchen (oder sowas wie eine Bigint-Klasse selber programmieren).

Allerdings lässt mich das
(2 p ) -1 ( 2 hoch p ) -1
wieder zweifeln.
Beim ersten verstehe ich 2 mal p -1

Steht das


> Beispiel Für p = 2 ist 2 2 -1 = 3 eine Primzahl oder für p= 3 ist 2 3 -1 = 7 eine Primzahl,
> aber x =2 11 -1 = 2047 ist keine Primzahl


auch so in der Aufgabenstellung?

edit: Deine höchste Primzahl ist 3571
Ein unsigned int kommt bis zu Zahlenwerten von 4294967295, also rund 4 Milliarden

(2^3571)-1 ist aber:
=9508554850410568696839441827625561356733871556707288357054599728032847914202118
68253794287764581576835988353348075927072662291473978400562295505879444359495815
16891535802491777606950878848376539992864893085269038802289721051003529989776963
81772651348690390313002051792853601926748364871850807065229722957632751249466545
74508172244855898882611618535289258974166724529784929229466287188174256748403186
37414191477340359612838440442622805733700456248083679235658852029933524812551569
24794583112283670387771177435431877124228143180950073514876882911924227283045390
15783782410193782069929720125837419484637577979561240882051615743077466988530530
24480227717212334884070271702107370083983879372748486720365581512799549579775802
68016257307717375849004921923545530120821924142119814767838050858463640719213346
58525024781603424791720970448038112024728162319728252869071124853986516943691952
77141092882154164498060660372475330937432870552522471946141915472602134254625182
79154895383952874385343615367502943824092760416444275100156469060590485948432434
675697069322678553853125685671886847

Kommt dir das nicht irgendwie seltsam vor?


----------



## braveheart10 (11. Dezember 2010)

ja hat der Prof. beschissen geschrieben.

nach dem z = (2^p ) -1 kommt wohl ein punkt und dann beginnt eine neue zeile mit ( 2 hoch p ) -1 Primzahlen sind, wenn p selbst eine Primzahl ist .

Hier hat einer aus meinem semester die aufgabe bereits gelöst - aber ich will diesen algorythmus nicht verwenden.
http://www.c-plusplus.de/forum/277033

er macht das ganze ja mit der modulo berechnung gut in dem programm sind nur die ersten 500 verlangt aber wenns dann dochmal grösser sein soll gehts mit dem sieb des eratosthenes oder atkin schneller.
http://geisswinkler.de/stefan/wordpress/wp-content/uploads/2008/02/diagramm.jpg


----------



## sheel (11. Dezember 2010)

Dein Kollege hat das aber alles andere als gelöst...
Schau dir mein edit oben an.
Da stoßen die eingebauten C-Variablen an ihre Grenzen.

Falls wir die Aufgabenstellung richtig verstehen, musst du wohl oder übel externe Bibliotheken nehmen oder einen eigenen Typ schreiben und für den alles vom Plus weg selbst implementieren.


----------



## braveheart10 (11. Dezember 2010)

oh ja sheel du hast natürlich recht das es kein sinn macht da weiter zu rechnen.

in dem anderen forum hat das auch schon jemand gepostet:

Im Prinzip müsste die Schleife so aufgebaut sein, als ob du alle 500 gefundenen Primzahlen prüfen willst. Nach dem fünften Fund (213-1 = 8191) kann jedoch schon abgebrochen werden.
Eine Rechnung von 23571-1 und die Auswertung, ob das Ergebnis eine Primzahl ist, kann nach wenigen Vorlesungen nicht gelöst werden (Stichwort BigInt).


----------



## braveheart10 (11. Dezember 2010)

Wir hatten erst ca. 10 Vorlesungen, wir sind noch gar nicht soweit um mit externen bibliotheken zu arbeiten.
Also kann man sagen mit unserem Wissenstand kann man die Aufgabe nicht 100% korrekt lösen!

Kannst du mir trozdem nochmal nen ansatz zeigen wie ich die ersten 500 primzahlen in nem array speichere um damit weiter zu rechnen.

P.S.: super kompetentes, schnelles und hilfsbereites forum - werd mich anmelden.


----------



## sheel (11. Dezember 2010)

braveheart10 hat gesagt.:


> Wir hatten erst ca. 10 Vorlesungen, wir sind noch gar nicht soweit um mit externen bibliotheken zu arbeiten.
> Also kann man sagen mit unserem Wissenstand kann man die Aufgabe nicht 100% korrekt lösen!



Wenn wir die Aufgabe richtig verstanden haben, ja.



braveheart10 hat gesagt.:


> Kannst du mir trozdem nochmal nen ansatz zeigen wie ich die ersten 500 primzahlen in nem array speichere um damit weiter zu rechnen.




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

char pr_feld[5000];  //Array der zu überprüfenden Zahlen (nur für 1/0 reicht char auch)
int i;              //Zählvariable
int j;              //Funktionsinterner Zähler

int primzahlen[500];//Neu
int primanzahl;//Ersatz für iii
 
int main(void)
{  
    for(i=0;i<5000;i++)pr_feld[i]=0;
    primanzahl=0;

    //Sieb des Eratosthenes
    for(i=2; i <= 5000; i++) 
    {
        if(!pr_feld[i])
        {
            primzahlen[primanzahl]=i;//Statt ausgeben abspeichern, ausgeben kann man danach extra
            primanzahl++;
            if(primanzahl>=500)break;
            
            for(j = 1;(j*i) <= (sizeof(pr_feld)/sizeof(char));++j) 
            {
                pr_feld[(j*i)] = 1;
            }
        }
    }

    //Jetzt ausgeben
    for(i=0;i<primanzahl;i++)printf("%d\t",primzahlen[i]);
    system("Pause");
    return 0;
}
```



braveheart10 hat gesagt.:


> P.S.: super kompetentes, schnelles und hilfsbereites forum - werd mich anmelden.



Willkommen bei tutorials.de


----------



## braveheart10 (11. Dezember 2010)

genau das hab ich gesucht, muchas gracias sheel!


----------

