Sieb des Eratosthenes

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.