Sieb des Eratosthenes

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.

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.

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!

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

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

Nein das bedeutet, dass calloc nicht deklariert ist. Suche einfach mal nach "man calloc" da steht alles Wissenswerte. Das geht übrigens auch mit anderen Standardfunktionen.

Poste mal was du bis jetzt hast, da hat sich sicherlich viel verändert. Auch ein sizeof(Datentyp), um zu schauen ob es auch wirklich 64Bit sind, wäre hilfreich.

knivil

Wie waere es denn mit den standardisiertem Typ uint64_t ?

GER_Moki

Bisher sieht es so aus:

#ifdef __cplusplus
#error Ich nutze C++
#endif

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

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

    printf("Groesse Zaehlweite: %d Bytes\n", sizeof(Zaehlweite));
    printf("Groesse Summe:      %d Bytes\n\n\n", sizeof(Summe));

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

    bool *prime = calloc(Zaehlweite, sizeof(*prime));
    if (prime == NULL) {
        perror(NULL);
        }
    prime[0] = 1;                                 // 1 ist nicht prim

    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("%llu\n\n", Summe);

    }

Laut sizeof() hat Zaehlweite 4 Bytes und Summe 8 Bytes, wäre also richtig. Trotzdem kommt anscheinend ein overflow zustande... Liegt es vielleicht daran, dass ich in und long long int addiere?

knivil schrieb:

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

naja iwann hatts mich halt auch gejuckt um dann meine behauptungen zu belegen musste ich das natürlich testen

knivil

Dann haettest du dich beim Eulerprojekt angemeldet ... z.B. so wie ich.

sizeof(*prime)

Hier wuerde ich sizeof(bool) schreiben.

Btw.: Man braucht fuer diese Aufgabe die Primzahlen zwischen 1 und 2 Mio in einem Array nicht vorhalten.

Größer gleich Zählweite ist natürlich Quatsch. Schau dir nochmal an, von wo bis wo du auf den Feld zugreifst.

_--

GER_Moki schrieb:

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

damit die schleifen schön optimiert werden

GER_Moki

Paul Müller schrieb:

Größer gleich Zählweite ist natürlich Quatsch. Schau dir nochmal an, von wo bis wo du auf den Feld zugreifst.

? Tut mir leid, aber ich hab im Moment keine Ahnung worauf du hinaus willst... Ich habe 3 größer-Zeichen im ganzen Code, aber die sind bei den 3 Include-Befehlen. Ich glaube eher, ich habe immer noch einen Overflow der Variable, kann aber im Moment nicht ausmachen, worans liegt

knivil schrieb:

sizeof(*prime)
Hier wuerde ich sizeof(bool) schreiben.

Das ändert an sich aber nichts, oder?

knivil schrieb:

Btw.: Man braucht fuer diese Aufgabe die Primzahlen zwischen 1 und 2 Mio in einem Array nicht vorhalten.

Nunja, nein. Ich könnte mir auch BruteForce oder eine beliebige andere Methode aussuchen

_-- schrieb:

damit die schleifen schön optimiert werden

Mit templates habe ich mich noch gar nicht beschäftigt und ich denke, da sind momentan andere Lücken wichtiger zu schließen