Primzahl in C



  • Guten Tag,

    ich habe folgenden Code erhalten, und soll diesen erklaeren koennen.
    Offenbar handelt es sich hierbei um einen Code, dessen Eingabe eine Zahl zwischen 2 und 1000 enthalten soll, und durch den Output gezeigt wird, ob es sich hierbei um eine Primzahl handelt oder nicht.

    Jedoch bin ich mir sehr unsicher ueber das, was im Programm genau geschieht. Ich benoetige hierzu eine wirklich ausfuehrliche Erklaerung.

    Vielen Dank!

     int main() {
     int zahl,i,j;              
    printf("Primzahlen  \nBitte geben Sie eine zahl zwischen zwei und tausend ein\n");      
    scanf("%d", &zahl);   
    int tab[zahl];                    
    for(i=0; i<zahl-1; i++) {     
     tab[i]=i+2;           } 
     for(i=2; i<zahl; i++){ 
     for(j=2; j<zahl; j++){      
      if(tab [j]%i==0 && tab[j]!=i){    
        tab[j]=0;}                  }         
      }      for(j=0; j<zahl-1; j++){
               printf("\t%d\n", tab [j]); 
              }           return 0; 
    }```

  • Mod

    Schreibe bitte in eine Zeile vor Deinen Code ``` und in eine Zeile nach deinem Code ```. Alternativ markiere Deinen Code und klicke auf das </> in der Symbolleiste über dem Eingabefeld.
    Du kannst Deine Beiträge auch im Nachhinein bearbeiten. Den Menüpunkt "Bearbeiten" findest Du in dem Drei-Punkte-Menü rechts unter Deinen Beiträgen.

    Dann kann man deinen Beitrag auch lesen und du bekommst brauchbare Antworten.

    Der Code hat <15 Zeilen. Kannst du etwas konkreter sein, was du nicht verstehst?

    Ansonsten kann ich mir den Kommentar nicht verkneifen, dass dieser Code krachend durch alle Reviews fallen würde. Ungeprüfter Stackoverflow. Obskure Variablennamen. Gemischter Stil bezüglich Variablendefinitionen. Und bestimmt noch viel mehr, das ich jetzt nicht sehe, wegen der unlesbaren Formatierung. Ganz schön viel für so kurzen Code. Die obskure Schreibweise kann man ja noch darauf schieben, dass man die Aufgabe schwierig machen möchte. Aber der potentielle Stackoverflow kann nur auf Inkompetenz geschoben werden.



  • Hi, danke fuer den Tipp.

    Ich verstehe nicht so ganz, was im Code gemacht wird bzw. wie da vorgegangen wird, um eine Primzahl ausgeben zu lassen. Es ware toll, wenn schrittweise erklaert werden koennte, was da genau gemacht wird.

    Auf die Schreibweise meiner Tutoren habe ich leider keinen Einfluss.


  • Mod

    Hast du das Programm mal ausgeführt? Vielleicht ist deine Annahme ja falsch, dass das Programm ausgibt, ob die eingegebene Zahl eine Primzahl ist…

    Nachdem du herausgefunden hast, was das Programm wirklich tut: Wenn du die umgekehrte Aufgabe hättest, ein Programm zu schreiben, welches das tut, was dieses Programm tut, wie würdest du vorgehen? Wahrscheinlich würde ein erster Versuch erst einmal anders aussehen, und total ineffizient sein. Aber was ist, wenn du wirklich clever vorgehen wolltest? Dann wirst du beim zweiten Versuch wahrscheinlich etwas wie hier erfinden. Und dann kannst du auch erklären, was hier passiert.

    Wobei das hier trotzdem auch eine sehr ineffiziente Lösung ist. Keine Ahnung, ob Absicht, oder nicht gekonnt. Denn es sieht fast so aus wie eine gut-gemeint-aber-nicht-gekonnt-Variante des wirklich guten Algorithmus. Wenn dich interessiert, was die wirklich gute Variante ist, dann googel mal danach. Du wirst sehen, dass schon die alten Griechen über dieses Problem nachgedacht haben, und wenigstens einer eine ganz clevere Lösung gefunden hat. Und dass diese Lösung ziemlich ähnlich aussieht wie das hier, bloß in gut.



  • @Fachidiot sagte in Primzahl in C:

    Auf die Schreibweise meiner Tutoren habe ich leider keinen Einfluss.

    Als Anmerkung: Die Funktionen der Standardlibrary müssen seit ANSI C1989 über ein Include in der Übersetzungseinheit bekannt gemacht werden. Da muss also ganz am Anfang

    #include <stdio.h>
    ...
    

    rein. Falls Du das vergessen hast, achte beim nächsten Mal unbedingt auf so etwas. Wenn es die Tutoren waren, nette Grüße aber das macht man seit 1989 nicht mehr so!!!

    Zum Programm schau Dir die von Null verschiedenen Zahlen an. Was haben diese gemein?



  • Ich hab den Code für dich mal vernünftig formatiert:

    #include <stdlib.h>
    
    int main() 
    {
       int zahl,i,j;              
       printf("Primzahlen  \nBitte geben Sie eine zahl zwischen zwei und tausend ein\n");      
       scanf("%d", &zahl);   
       int tab[zahl];                    
       for(i=0; i<zahl-1; i++) 
       {     
          tab[i]=i+2;          
       } 
       for(i=2; i<zahl; i++)
       { 
          for(j=2; j<zahl; j++)
          {      
             if(tab [j]%i==0 && tab[j]!=i)
             {    
                tab[j]=0;
             }                  
          }
       }         
       for(j=0; j<zahl-1; j++)
       {
          printf("\t%d\n", tab [j]); 
        }           
       return 0; 
    }
    

    Wie kommt´s eigentlich, dass SeppJ oft was Ähnliches postet wie ich vorhabe, nur in ausführlich und auch noch 30 Sekunden schneller?
    It´s a conspiracy...



  • @SeppJ Ich wuerde mir als erstes ueberlegen, wie man die mathematische Strategie



  • @SeppJ sagte in Primzahl in C:

    Wenn dich interessiert, was die wirklich gute Variante ist, dann googel mal danach.

    Bevor er/sie/es sich noch einen Wolf sucht: Sieve of Eratosthenes

    @Fachidiot sagte in Primzahl in C:

    @SeppJ Ich wuerde mir als erstes ueberlegen, wie man die mathematische Strategie

    Da fehlen ein Wörter.



  • @DocShoe sagte in Primzahl in C:

    Ich hab den Code für dich mal vernünftig formatiert:

    Hm, halte ich aufgrund deiner Spaces nicht für vernünftig:

    if(tab [j]%i==0 && tab[j]!=i)

    Das wäre bei mir: if (tab[j] % i == 0 && tab[j] != i)

    Und das hier: int zahl,i,j; wäre int zahl, i, j; - wobei man da natürlich noch sagen muss: warum werden diese Variablen im Scpoe von main deklariert?

    #include <stdlib.h>

    Meintest du: #include <stdio.h>?


  • Mod

    @wob sagte in Primzahl in C:

    wobei man da natürlich noch sagen muss: warum werden diese Variablen im Scpoe von main deklariert?

    @SeppJ sagte in Primzahl in C:

    Gemischter Stil bezüglich Variablendefinitionen. […] kann nur auf Inkompetenz geschoben werden.



  • NoLess-Bullshit Version:

    #include <limits.h>   // CHAR_BIT
    #include <stdbool.h>  // bool, true, false
    #include <stdlib.h>   // malloc(), free(), EXIT_FAILURE
    #include <stdio.h>    // scanf(), fputs(), printf()
    #include <string.h>   // memset()
    #include <math.h>     // sqrt()
    
    typedef char unsigned byte_t;
    
    void set_bit(byte_t *byte, size_t bit, bool value)
    {
        *byte ^= (-value ^ *byte) & (1u << bit);  // 1)
    
        /* Plan B (faster on superscalar CPUs):
        byte_t mask = 1u << bit;
        *byte = (*byte & ~mask) | (-value & mask);
        */
    }
    
    bool get_bit(byte_t const *byte, size_t bit)
    {
        return *byte & (1u << bit);
    }
    
    void sieve_set(byte_t *sieve, size_t index, bool value)
    {
        size_t byte = index / CHAR_BIT;
        size_t bit = index % CHAR_BIT;
        set_bit(&sieve[byte], bit, value);
    }
    
    bool sieve_get(byte_t const *sieve, size_t index)
    {
        size_t byte = index / CHAR_BIT;
        size_t bit = index % CHAR_BIT;
        return get_bit(&sieve[byte], bit);
    }
    
    int main()
    {
        printf("Number to test: ");
        long number;
        if (scanf("%ld", &number) != 1 || number < 1) {
            fputs("Input error :(\n\n", stderr);
            return EXIT_FAILURE;
        }
    
        size_t sieve_size = (size_t)number / CHAR_BIT + 1;
        byte_t *sieve = malloc(sieve_size * sizeof(*sieve));
        if (!sieve) {
            fputs("Not enough memory :(\n\n", stderr);
            return EXIT_FAILURE;
        }
    
        memset(sieve, -1, sieve_size);
        sieve_set(sieve, 1, false);
    
        long const limit = sqrt(number);
        for(long i = 2; i <= limit; ++i)
            if (sieve_get(sieve, i))
                for (long long k = (long long)i * i; k <= number; k += i)  // 2)
                    sieve_set(sieve, k, false);
    
        printf("%ld is %sprime.\n\n", number, sieve_get(sieve, number) ? "" : "not ");
    
        free(sieve);
    }
    

    1) Bit Twiddling Hacks - Conditionally set or clear bits without branching
    2) long war eine blöde Wahl für k Wenn man LONG_MAX * LONG_MAX haben will.
    3) Alle Primes in 31 Bit ausgeben dauert literally ewig:

    ...
    2147477399 2147477419 2147477443 2147477467 2147477473 2147477503 2147477513
    2147477531 2147477533 2147477599 2147477627 2147477681 2147477687 2147477699
    2147477701 2147477737 2147477807 2147477809 2147477833 2147477851 2147477861
    2147477873 2147477879 2147477881 2147477933 2147477953 2147477989 2147478013
    2147478017 2147478049 2147478079 2147478083 2147478089 2147478127 2147478133
    2147478149 2147478253 2147478259 2147478293 2147478299 2147478331 2147478349
    2147478373 2147478461 2147478481 2147478491 2147478497 2147478503 2147478517
    2147478521 2147478563 2147478569 2147478581 2147478601 2147478611 2147478647
    2147478649 2147478653 2147478659 2147478661 2147478673 2147478701 2147478703
    2147478719 2147478721 2147478727 2147478731 2147478733 2147478763 2147478791
    2147478821 2147478859 2147478863 2147478889 2147478899 2147478911 2147478919
    2147478937 2147478959 2147478961 2147478967 2147478997 2147479013 2147479031
    2147479057 2147479063 2147479079 2147479091 2147479097 2147479121 2147479129
    2147479133 2147479171 2147479189 2147479231 2147479259 2147479273 2147479307
    2147479339 2147479349 2147479361 2147479381 2147479403 2147479421 2147479447
    2147479489 2147479507 2147479513 2147479517 2147479531 2147479547 2147479549
    2147479573 2147479589 2147479601 2147479619 2147479637 2147479643 2147479657
    2147479681 2147479751 2147479753 2147479757 2147479781 2147479787 2147479819
    2147479823 2147479879 2147479891 2147479897 2147479907 2147479937 2147479991
    2147480009 2147480011 2147480039 2147480161 2147480197 2147480207 2147480219
    2147480227 2147480297 2147480299 2147480311 2147480327 2147480369 2147480429
    2147480437 2147480459 2147480471 2147480507 2147480519 2147480527 2147480551
    2147480591 2147480611 2147480623 2147480641 2147480651 2147480677 2147480683
    2147480707 2147480723 2147480743 2147480747 2147480791 2147480837 2147480843
    2147480849 2147480893 2147480897 2147480899 2147480921 2147480927 2147480941
    2147480957 2147480969 2147480971 2147480989 2147481019 2147481031 2147481053
    2147481071 2147481139 2147481143 2147481151 2147481173 2147481179 2147481199
    2147481209 2147481247 2147481263 2147481269 2147481283 2147481311 2147481317
    2147481337 2147481353 2147481359 2147481367 2147481373 2147481487 2147481491
    2147481499 2147481509 2147481529 2147481563 2147481571 2147481629 2147481673
    2147481793 2147481797 2147481811 2147481827 2147481863 2147481883 2147481893
    2147481899 2147481901 2147481907 2147481937 2147481949 2147481967 2147481997
    2147482021 2147482063 2147482081 2147482091 2147482093 2147482121 2147482223
    2147482231 2147482237 2147482273 2147482291 2147482327 2147482343 2147482349
    2147482361 2147482367 2147482409 2147482417 2147482481 2147482501 2147482507
    2147482577 2147482583 2147482591 2147482621 2147482661 2147482663 2147482681
    2147482693 2147482697 2147482739 2147482763 2147482801 2147482811 2147482817
    2147482819 2147482859 2147482867 2147482873 2147482877 2147482921 2147482937
    2147482943 2147482949 2147482951 2147483029 2147483033 2147483053 2147483059
    2147483069 2147483077 2147483123 2147483137 2147483171 2147483179 2147483237
    2147483249 2147483269 2147483323 2147483353 2147483399 2147483423 2147483477
    2147483489 2147483497 2147483543 2147483549 2147483563 2147483579 2147483587
    2147483629 2147483647 is prime.
    

    yay.

    Sieben aller 31 Bit auf einem AMD-FX4300 @ 3.9 GHz netto 35.756 s.


Log in to reply