Sieb des Eratosthenes

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

Wutz

GER_Moki schrieb:

knivil schrieb:
sizeof(*prime)
Hier wuerde ich sizeof(bool) schreiben.

Auch nichts verstanden und nicht für 1 Cent weitergedacht.
Was muss man ändern, falls man den Typ des Zeigers mal ändern möchte, z.B. von bool auf int oder struct oder...?
Richtig, mit eben genannten Laiencode beide Seiten der Zuweisung, bei voriger Variante nur 1x links.

knivil

Kacken kann ich auch. Natuerlich muss der restliche Code nicht dem neuen Datentyp angepasst werden ... und ich sehe nicht sofort, wie viel Speicher tatsaechlich angefordert wird.

Wutz

knivil schrieb:

Wie waere es denn mit den standardisiertem Typ uint64_t ?

Das ist nur C99, jeder C89 also auch MSVC wird daran scheitern.

GER_Moki

Wutz schrieb:

knivil schrieb:

Wie waere es denn mit den standardisiertem Typ uint64_t ?

Das ist nur C99, jeder C89 also auch MSVC wird daran scheitern.

Deswegen sollte es doch trotzdem mit

long long int

und Compiler auf C99-Standard fuktionieren? Oder muss ich dazu das in Strings umwandeln bzw eine Bibliothek (wie die BigNum Library) verwenden?

knivil

Vielleicht kommst du ja selbst drauf ....

GER_Moki

knivil schrieb:

Vielleicht kommst du ja selbst drauf ....

Vielleicht, vielleicht auch nicht...

142913828922 - 1179908154 = 141733920768 = 2^32 * 33

Also läuft Summe genau 33mal über und es bleiben 1179908154 (mein Ergebnis) über. Aber warum?
Ein Bekannter hat das mit gcc 4.5.0, Linux x86-64 compiliert, da funktioniert es einwandfrei. Hier mit gcc 3.4.2, win32 gehts nicht, da läuft das Ding über

knivil

Ein Bekannter hat das mit gcc 4.5.0, Linux x86-64 compiliert, da funktioniert es einwandfrei.

Weil sein Ganzzahltyp eben schon von Haus aus 64 Bit ist ...

GER_Moki

Öhm... Ich glaube, ich habe des Rätsels Lösung *schäm*:

GCC-Update hat das Problem gelöst

Vielen Dank für eure Hilfe! An den Compiler habe ich gar nicht gedacht...

Wutz

GER_Moki schrieb:

Deswegen sollte es doch trotzdem mit
long long int
und Compiler auf C99-Standard fuktionieren? Oder muss ich dazu das in Strings umwandeln bzw eine Bibliothek (wie die BigNum Library) verwenden?

long long ist ebenso kein C89, wird aber z.B. von neueren MSVC unterstützt (allerdings mit eigenen printf/scanf Formatspezifizierern und somit nicht portabel).

Wutz

Ich habe deine Siebimplementierung nicht verstanden und mal was einfaches genommen, es werden nur notwendige Zaehlweite+1 Bytes belegt und mit 0 initialisert. long long ist kein C89, deshalb hier erstmal nur eine Überlausprüfung.

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

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

/* Sieb des Erathostenes
*/
int main(int argc, char *argv[])
{
    unsigned long i,j,k,Zaehlweite,
    Summe = 0;
    unsigned char *prime;

    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? ");
    printf("Zaehlweite: %lu \n", Zaehlweite);
    printf("Summe:      %lu \n\n\n", Summe);

    if( 1!=scanf("%lu", &Zaehlweite) ) return fputs("scanf()",stderr),1;
    prime = calloc(1,(Zaehlweite+1)*sizeof*prime); /* Hier wird alles mit 0 initialisiert */
    if( !prime ) return perror("malloc(prime)"),1;

    for( i=2; i<=Zaehlweite ; ++i )
      if(prime[i]==0)
        for( j=i<<1; j<=Zaehlweite ; j+=i )
          prime[j]=1; /* Vielfaches als Primzahl ausblenden */

    for( k = 2; k <= Zaehlweite; k++) {
            if(prime[k] == 0) {
                        if( Summe+k<Summe) puts("Überlauf!");
                        Summe += k;
                        }
            }

    printf("%lu, ", Summe);

    free(prime);
    return EXIT_SUCCESS;
}

GER_Moki

Wutz schrieb:

Ich habe deine Siebimplementierung nicht verstanden und mal was einfaches genommen, es werden nur notwendige Zaehlweite+1 Bytes belegt und mit 0 initialisert. long long ist kein C89, deshalb hier erstmal nur eine Überlausprüfung.

Ist die Implementierung von mir so undurchsichtig? Ich bin am überlegen, ob ich die Summe als int-Array implementieren soll und bei einem Überlauf vorher soviel abziehe und gleichzeitig das Element eine weiter um 1 erhöhe...