Sieb des Eratosthenes

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

knivil

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.

GER_Moki

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.

knivil

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.

GER_Moki

Ist die GMP Library C konform? Oder gibt es andere bessere?

knivil

Nimm die einfach. (Ohne mal zu hinterfragen, was du mit C-konform meinst.)

Ich hasse es wie in diesem Forum immer wieder auf Anfänger herumgehackt wird. "Les ein Buch das ist Grundlage" omg wenn ihr nicht helfen wollt dann lass es doch einfach.

GER_Moki

knivil schrieb:

Nimm die einfach. (Ohne mal zu hinterfragen, was du mit C-konform meinst.)

C-konform = versteht das der C-Compiler oder brauche ich einen C++-Compiler?

Wutz

Für die Behandlung großer Zahlen außerhalb der Integerbereiche des Compilers bieten sich diverse Bibliotheken an, z.B. auch

http://spinning-yarns.org/michael/mpi/

was als ANSI C implementiert ist um gleich sinnfreien Mutmaßungen über die Sinnhaftigkeit von Standards entgegenzutreten.