4. Sieb des Eratosthenes

Sieb des Eratosthenes

  • G

    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 😞

    0
  • ?

    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.

    0
  • ?

    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.

    0
  • K

    Wie waere es denn mit den standardisiertem Typ uint64_t ?

    0
  • G

    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?

    0
  • ?

    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 😞

    0
  • K

    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.

    0
  • ?

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

    0
  • _

    GER_Moki schrieb:

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

    damit die schleifen schön optimiert werden 🤡

    0
  • G

    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 😉

    0

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

    0
  • K

    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.

    0

  • knivil schrieb:

    Wie waere es denn mit den standardisiertem Typ uint64_t ?

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

    0
  • G

    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?

    0
  • K

    Vielleicht kommst du ja selbst drauf ....

    0
  • G

    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 😞

    0
  • K

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

    0
  • G

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

    0

  • 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).

    0

  • 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;
}
    0
Anmelden zum Antworten