Sieb des Eratosthenes

[GER_Moki]

Hallo,
ich habe, nachdem ich bisschen durch diverse C-Tutorials gelesen und probiert habe, die Seite http://projecteuler.net/ gefunden. Dort hänge ich jetzt so halb bei Aufgabe 10. Ich habe mir gedacht, schreib ein Programm, dass alle Primahlen in einem Zahlenraum mithilfe des Sieb des Eratosthenes aussiebt und mir die Zahlen danach aufaddiert und ausgibt.
Für kleine Zahlen funktioniert das ganze auch soweit, aber sobald ich die 2.000.000 als Grenze angebe, wird etwas falsches ausgegeben... Woran liegt das?

Außerdem würde ich gerne wissen, warum ein bool-Array mit 3 Millionen oder mehr Elementen einen Fehler ausgibt?

Gruss,
Moki

#include <cstdlib>
#include <iostream>

using namespace std;

// Suche nach der Summer aller Primzahlen kleiner als 2000000, Sieb des Erathostenes
int main(int argc, char *argv[])
{
    int Zaehlweite = 0;
    int Summe = 0;
    int Teiler = 1;
    bool prime[2000000];

    prime[0] = 1;                                 // 1 ist nicht prim
    for(int i = 1; i<=2000000; i++) {             // alle Bool ausser "1" auf 0 setzen, wenn am Ende prime[i]=0, dann ist i-1 prim
            prime[i] = 0;
            }

    printf("Dieses Programm gibt die Summe aller Primzahlen bis zu einer gewissen Obergrenze,\n maximal jedoch bis 2.000.000 aus.\n\n");
    printf("Bis zu welcher Zahl sollen die Primzahlen addiert werden? ");
    scanf("%i", &Zaehlweite);

    for(int Zaehler = 0; Zaehler <= Zaehlweite; Zaehler++) {
            if(prime[Zaehler] == 0) {
                          Teiler = Zaehler + 1;             // Teiler auf naechste Primzahl setzen

                          for(int j = 2; j * Teiler <= Zaehlweite; j++) {
                                  int Nicht_Prime = j * Teiler - 1;
                                  prime[Nicht_Prime] = 1;
                                  }
                          }           
            }

    for(int k = 0; k < Zaehlweite; k++) {
            if(prime[k] == 0) {
                        Summe = Summe + k + 1;

                        }
            }

    printf("%i, ", Summe);

    system("PAUSE");
    return EXIT_SUCCESS;
}

PS: System ist WinXP 32bit.

PPS: Nicht hauen, wenn es das falsche Subforum ist

[_--]

evtl. läuft dir der int über? hab aber die prims noch nie zusammengezählt. bitfields in c++ schauen übrigens so aus...

// bitset::operator[]
#include <iostream>
#include <bitset>
using namespace std;

int main ()
{
  bitset<4> mybits;

  mybits[1]=1;             // 0010
  mybits[2]=mybits[1];     // 0110

  cout << "mybits: " << mybits << endl; 

  return 0;
}

[__--]

also bei mir kommt nach <1 sek 142913828922 raus kann das stimmen

[__--]

hier das c++ gefrickle...

#include <iostream>
#include <bitset>
using namespace std;

template<size_t N>
unsigned long long prim_calc(){
  bitset<N> mybits;
  unsigned long long ret = 0;

  for(size_t i = 2; i < N;i++){
    if(0 == mybits[i]){
      for(size_t z = 2; z*i < N;z++){
        mybits[z*i] = 1;
      }
    }
  }

  for(size_t z = 2; z < N;z++){
    if(0 == mybits[z]){
      ret += z;
    }
  }
  return ret;
}

int main ()
{
  cout << "========================" << endl;
  cout << "sum:" << prim_calc<2000001>() << endl;

  return 0;
}

[GER_Moki]

__-- schrieb:

also bei mir kommt nach <1 sek 142913828922 raus kann das stimmen

Jepp, das Ergebnis stimmt: 142913828922.

Dass mir der int überläuft, darauf bin ich noch gar nicht gekommen Aber auch mit long long int (das ja einen Werteberech von 19 Dezimalstellen hat) kommt bei mir 1179908154 raus.

bitset<4> reserviert nur 4 Bit mit dem Namen mybits? Diese kann ich dann wie einen Array behandeln?

Und warum muss ich das mit C++ in ein Template auslagern?

[Wutz]

Falsches Forum, das ist wie jeder sehen kann, C++.

[GER_Moki]

Wutz schrieb:

Falsches Forum, das ist wie jeder sehen kann, C++.

Ich nutze Dev-Cpp. Wenn ich dort anklicke als C-Programm compilieren gibt der Compiler keinen Fehler aus, deshalb dachte ich, das passt auch hier hin. Was in dem Code gehört denn zu C++?

[Wutz]

Die ersten 4 Zeilen sind komplett C++.
Die akzeptiert KEIN C Compiler.

Testen kannst du das z.B. durch Einfügen von:

#ifdef __cplusplus
#error ich arbeite mit C++
#endif

Warum nutzt du diese veraltete IDE?
Für C Programmierung bietet sich z.B. auch CodeBlocks an (eine IDE mit integriertem GNU C Compiler)

[GER_Moki]

Wutz schrieb:

Die ersten 4 Zeilen sind komplett C++.
Die akzeptiert KEIN C Compiler.

Gibt es dazu auch ein Pendant in C? Oder macht das nichts?

Wutz schrieb:

Testen kannst du das z.B. durch Einfügen von:

#ifdef __cplusplus
#error ich arbeite mit C++
#endif

Hab ich gemacht, gibt nen Fehler aus

Wutz schrieb:

Warum nutzt du diese veraltete IDE?
Für C Programmierung bietet sich z.B. auch CodeBlocks an (eine IDE mit integriertem GNU C Compiler)

Weil ich noch nicht an ihre Grenzen gestossen bin und mir niemand eine bessere empfohlen hat. Ich schau mir CodeBlocks mal an

[Wutz]

#include <iostream> /* in C ungefähr: <stdio.h> */
#include <bitset>   /* in C unnötig */
using namespace std; /* in C kein Äquivalent */

template<size_t N>  /* in C kein Äquivalent */

Vielleicht nochmal zum Verständnis:

Man kann mit einem C++ Compiler auch reinen C Code fehlerfrei compilieren, dazu bedarf es allerdings der genauen Kenntnis der durchaus vorhandenen (und von Laien meist ignorierten) Unterschiede beider Sprachen; leider ist es aber oft bei Laien so, dass sie von einem C++ Programm sprechen, obwohl fast alles reiner C Code ist.

[Paul Müller]

Zu deinem Boolean-Array mit ganz vielen Feldern würde ich sagen, dass passt nicht auf deinen Stack. So große Werte musst du auf dem Heap allokieren.

[GER_Moki]

Paul Müller schrieb:

Zu deinem Boolean-Array mit ganz vielen Feldern würde ich sagen, dass passt nicht auf deinen Stack. So große Werte musst du auf dem Heap allokieren.

Der wer muss auf die was gemacht werden? Tut mir leid, ich verstehe gerade nur Bahnhof (Memo an mich: Was ist Heap, was ist Stack, wie allokiert man?)
Ich habe das ganze jetzt schon mithilfe von

bitset<N>

geändert. Die brauchen ja dann nur ein Bit pro Wert, wenn ich das richtig verstanden habe? Wären also bei 2 Millionen Zahlen etwa 2MB Speicher, der gebraucht wird.

[Paul Müller]

GER_Moki schrieb:

Der wer muss auf die was gemacht werden? Tut mir leid, ich verstehe gerade nur Bahnhof (Memo an mich: Was ist Heap, was ist Stack, wie allokiert man?)

Das sind Grundlagen. Wenn du dich damit nicht beschäftigen willst, dann programmiere irgendwas anderes, aber kein C.

GER_Moki schrieb:

Ich habe das ganze jetzt schon mithilfe von

bitset<N>

geändert.

Was kein C ist und dich auch nicht davor bewahrt irgendwann auf den Boden der Tatsachen zurück geholt zu werden. Nochmal lerne die Grundlagen!
Ein schönes Beispiel dazu sind die drei Quelltexte und die Frage dazu. Worauf leider nicht weiter eingegangen wird. http://www.c-plusplus.net/forum/279085

GER_Moki schrieb:

Wären also bei 2 Millionen Zahlen etwa 2MB Speicher, der gebraucht wird.

Typische Stackgröße ist 1MB, soweit ich mich erinnere. Und da landen noch die ganzen Werte von deinen anderen Funktionen drauf. bitset selber wird aber vermutlich intern auf dem Heap arbeiten, allein um den Stack nicht zu sprengen.

[knivil]

__-- schrieb:

also bei mir kommt nach <1 sek 142913828922 raus kann das stimmen

Das ist nicht die Frage ... was soll der Scheiss? Wenn es darum ging, dann findet er die Loesungen zu den Raetseln auchim Internet.

Btw. Fuer die Summe an sich braucht man einen Integer mit mehr als 32 Bit.

[GER_Moki]

Paul Müller schrieb:

Wenn du dich damit nicht beschäftigen willst, dann programmiere irgendwas anderes, aber kein C.

...

OK, Stack und Heap sind nun einigermaßen klare Begriffe. Was welcher Speicher macht, wieso der Stack nicht so groß ist...

Macht es dann Sinn mit calloc() mir Speicher aus dem Heap zu holen und dort dann quasi meine Bits zu speichern? Mal testen!

[Paul Müller]

Als einfache Regel kann man sagen, immer wenn es etwas "mehr" Speicher sein soll, den Heap zu verwenden. Das ist aber nur eine ganz einfache Betrachtung, die für den Anfang reicht. Um den Stack wirst du in jedem Fall nicht herum kommen und das ist auch gut so. Kleine Objekte machen sich dort sehr gut. Auch ist es rein Programmiertechnisch kein allzu großer Unterschied. Weil Daten die für den Stack zu groß werden können, sind in der Regel nur Felder und der Zugriff ist dabei gleich. Der große Nachteil von dynamischen Feldern ist, du musst dir ihre Größe merken und sie nach Gebrauch wieder freigeben.
Konkret sieht das so aus:

bool prime[20];
// wird zu
bool * prime = calloc(20, sizeof(*prime));
if (prime == NULL)
{
  perror(NULL);
  exit(1);
}

// hier gehts genauso weiter, wie vorher

// und wenn du prime nicht mehr brauchst
free(prime);

Merken musst du dir dabei die Anzahl der Elemente (hier 20) und den Zeiger, der von calloc() kam, für das free(). calloc() setzt zusätzlich noch alle Werte auf 0, bei bool also false.
Die Überprüfung ist übrigens wichtig. Das du sie sonst nicht machen musst ist ein weiterer Nachteil von Variablen auf dem Stack. Du merkst es nicht, ob sie angelegt werden konnten. Deswegen macht dein Programm auch irgendwas und du wunderst dich dann.

[GER_Moki]

Paul Müller schrieb:

bool prime[20];
// wird zu
bool * prime = calloc(20, sizeof(*prime));
if (prime == NULL)
{
  perror(NULL);
  exit(1);
}

// hier gehts genauso weiter, wie vorher

// und wenn du prime nicht mehr brauchst
free(prime);

calloc() gibt doch void zurück. Muss ich den Datentyp dann noch casten? Also so:

bool *prime = (bool *)calloc(2000000, sizeof(*prime));

Paul Müller schrieb:

Die Überprüfung ist übrigens wichtig. Das du sie sonst nicht machen musst ist ein weiterer Nachteil von Variablen auf dem Stack. Du merkst es nicht, ob sie angelegt werden konnten. Deswegen macht dein Programm auch irgendwas und du wunderst dich dann.

Die Überprüfung besagt, dass falls der Speicher nicht allokiert werden konnte, ein Fehler ausgegeben wird? Der Speicher, der allokiert werden kann ist aber nur von meinem verfügbaren RAM abhängig oder gibt es dort auch Einschränkungen? Die Suche im www hat mir da keine schlüssigen Infos geben können

[Paul Müller]

GER_Moki schrieb:

calloc() gibt doch void zurück. Muss ich den Datentyp dann noch casten?

Kann sein, im Zweifelsfall meckert der Compiler.

GER_Moki schrieb:

Die Überprüfung besagt, dass falls der Speicher nicht allokiert werden konnte, ein Fehler ausgegeben wird?

korrekt

GER_Moki schrieb:

Der Speicher, der allokiert werden kann ist aber nur von meinem verfügbaren RAM abhängig oder gibt es dort auch Einschränkungen?

Es gibt dabei verschiedene Einschränkungen. Die entscheidende ist aber, ob der von der angeforderte Platz, an einem Stück, verfügbar ist. Der tatsächlich vorhandener RAM spielt dabei keine Rolle. Das Betriebssystem gibt dir einen virtuellen Speicher. Der ist bei Windows 32Bit immer 2GB, auch wenn du nur 256MB hast. Das ist aber mehr eine theoretisch nutzbare Größe, die auch von der Auslagerungsdatei, etc. abhängt.

[Wutz]

Paul Müller schrieb:

GER_Moki schrieb:

calloc() gibt doch void zurück. Muss ich den Datentyp dann noch casten?

Kann sein, im Zweifelsfall meckert der Compiler.

Kann nicht sein.
calloc liefert genau das zurück, was im Standard spezifiziert ist nämlich void*.
Casten muss man dies nur, wenn man C Code mit einem C++ Compiler übersetzen will, denn bei C++ führt ein fehlender Cast zu einem Fehler. An einem Cast bei *alloc erkennt man auch diejenigen, welche nicht wissen was sie tun (C oder C++).

[GER_Moki]

Wutz schrieb:

An einem Cast bei *alloc erkennt man auch diejenigen, welche nicht wissen was sie tun (C oder C++).

Woher als Anfänger wissen, wenn es in keinem Tut drinsteht?

So, jetzt habe ich den Code nochmal als .c gespeichert, den C99 Standard für den Compiler ausgewählt, compiliert und habe (noch immer eine Warnung):

|18|warning: implicit declaration of function `calloc'|

Bedeutet das, calloc() wird hier erst deklariert? Ich kann mit der Fehlermeldung leider überhaupt nichts anfangen

edit:#include <stdlib.h> hat geholfen

Jetzt tut sich mir aber eine nächste Frage auf:
Ich habe die Summe der Primzahlen jetzt als

unsigned long long int

deklariert (Ausgabe auch auf %llu geändert). Die 64bit sollten für die angepeilten 2 Millionen doch allemal reichen? Er gibt mir aber wieder etwas falsches aus...

Tut mir Leid, dass ich lauter Anfängerfragen stelle, aber laut Recherche sollte das eigentlich funktionieren