4. Sieb des Eratosthenes

Sieb des Eratosthenes

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

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

    0
  • K

    Ich verstehe nicht, warum ihr auf C89 und C99 so rumreitet. Man schaetzt das Ergebnis ab und waehlt dementsprechend seinen Datentyp. Ich habe unint64_t vorgeschlagen. Die Header mit den entsprechenden typedefs gibt es auch fuer MSVC. Und durch dein Compilerupdate ist einfach fuer long long int ein anderes DEFINE oder typedef da und es funktioniert deshalb. Eine eigene Loesung mit Int-Arrays zu bauen ist einfach Bullshit. Genau wie auf portabel beim Eulerprojekt herumzureiten.

    0
  • G

    knivil schrieb:

    Ich verstehe nicht, warum ihr auf C89 und C99 so rumreitet. Man schaetzt das Ergebnis ab und waehlt dementsprechend seinen Datentyp. Ich habe unint64_t vorgeschlagen. Die Header mit den entsprechenden typedefs gibt es auch fuer MSVC. Und durch dein Compilerupdate ist einfach fuer long long int ein anderes DEFINE oder typedef da und es funktioniert deshalb. Eine eigene Loesung mit Int-Arrays zu bauen ist einfach Bullshit. Genau wie auf portabel beim Eulerprojekt herumzureiten.

    *g* Locker bleiben 😉 Die nächste Aufgabe ist es die Quersumme von 2^1000 und 100! zu berechnen. Da werden auf 64bit Zahlen versagen. Also teste ich das hier, weil ich weiß, was rauskommen muss.

    0
  • K

    Dann wuerde ich dir eine Bibliothek empfehlen, die Ganzahlen beliebiger Groesse bereitstellt. Fuer Problem 20 wird die Zahl etwa 525 Bits beanspruchen. Du kannst aber auch einen Weg suchen, ohne grosse Zahlen benutzen zu muessen.

    0
Anmelden zum Antworten