Generierung von Primzahlen innerhalb eines Bereichs in C ++

  • Ich hatte ein Problem, um alle Primzahlen in einem Bereich herauszufinden. Kurz nachdem ich das Programm geschrieben hatte, fand ich zahlreiche andere Codes, um das Problem zu lösen. Ich möchte wissen, ob mein Algorithmus effizient ist. Ist es wie Siebfiltration? (vor dem Schreiben dieses Codes hatte ich keine klare Vorstellung von der Siebfiltermethode) oder der verwendete Algorithmus ist schlecht?

     #include<iostream.h>
    #include<math.h>
     
    < h3> prime_gen
     void prime_gen(int a,int b)
    {
        int array[4]={2,3,5,7},holder[1000000]={0},count=0,flag=0,length=0,number_count=0;
    
        for(int i=0;i<b;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(i==array[j])
                {
                    break;
                }
                else
                {
                    if(i%array[j]==0)
                    {
                        count++;
                    }
                }
            }
            if(count==0)
            {
                if(i>1)
                {
                    holder[length++]=i;
                }
                else
                {
                    length=0;
                }
            }
            count=0;
        }   
    
        if(length==0)
        {   
            cout<<"No prime numbers exist within the range";
            cout<<"\n";
        }                               
        else 
        {                                                               
            cout<<"Prime numbers are:";
    
            for(int i=0;i<length;i++)
            {                                                                                   
                int t=holder[i];
    
                for(int check=0;check<sqrt(length);check++)
                {
    
                    if(t!=holder[check])
                    {
                        if(t%holder[check]==0)
                        {
                            t=0;
                        }
                    }
                }
    
                if(t!=0&&t>=a)
                {
                    number_count++;
                    cout<<t<<"\t";
                }
            }
    
            cout<<"Total count:"<<number_count<<endl;
        }
    }
     

    main

     int main()
    {
        int a,b;
    
        cout<<"Put the first integer:";
        cin>>a;
    
        cout<<"Put the second integer:";
        cin>>b;
    
        prime_gen(a,b);
    }
     
    04 May 2015
    CaridorcMiNdFrEaK
4 answers
  • Stilistische Notizen:

    • Verwenden Sie mehr Leerzeichen um die Interpunktion (for(int i=0;i<b;i++) möchte browsen), streuen Sie Ihren Code nicht mit Leerzeichen Zeilen an zufälligen Stellen und verwenden konsistente Einrückungen.
    • Deklarieren Sie Ihre Variablen in separaten Zeilen. Verwenden Sie das leere Feld auf der rechten Seite, um einen Kommentar zu schreiben, in dem erklärt wird, wofür die Variable bestimmt ist.
    • Verwenden Sie sinnvolle Variablennamen. Komm schon, array? Der Leser kann sehen, dass es sich um ein Array handelt, aber was enthält es?

    Denken Sie auch darüber nach: Sie schreiben C ++, nicht C Einige Teile (wie die Verwendung von C-Arrays) sind jedoch nicht idiomatisches C ++; Sie sollten eines auswählen, entweder C (und verwenden Sie stdio, nicht iostream) oder C ++ (und verwenden Sie new und die STL). Da ich ein C-Programmierer bin, aber nicht viel C ++ beherrsche, werde ich die C-ish-Teile kommentieren und nichts zu idiomatischem C ++ sagen.

    The array Variable ist hier nicht nützlich. Die kleinen Primzahlen erscheinen ohnehin im Array holder, setzen Sie sie also direkt ein. Selbst wenn Sie kleine Primzahlen speziell behandelt haben, ist Ihre count -Variable unbrauchbar: Sie müssen nicht zählen, wie viele kleine Primzahlen i teilen, Sie müssen nur wissen, ob einige kleine Primzahlen i.

    Sie können auch vorzeichenlose Ganzzahlen für Ihre Variablen verwenden, da diese keine negativen Zahlen enthalten.

     unsigned holders[1000000]; /* list of prime numbers */
    unsigned length = 0;
    holders[length++] = 2;
    holders[length++] = 3;
    holders[length++] = 5;
    holders[length++] = 7;
     

    Sie müssen holders nicht vollständig initialisieren, da Sie nur die ersten length -Elemente betrachten. Während Sie schreiben könnten unsigned holders[1000000] = {3, 5, 7}; und der Compiler den Rest mit Nullen füllen würde, würde dies bei typischen Implementierungen dazu führen, dass das gesamte Array (einschließlich Nullen) in Ihre ausführbare Datei geschrieben wird. Dies ist eine große Verschwendung.

    Sie sollten die holders sowieso dynamisch zuweisen und ihre Größe überprüfen. Wenn jemand einen so großen Wert für b übergibt, dass das Array holders überläuft, überschreibt Ihr Code einen beliebigen Speicherplatz. Berechnen Sie entweder die Größe des Arrays holders, sodass es & #

    15 November 2011
    Joseph Daigle
  • Ihr Code ist nicht korrekt, daher ist die Effizienz nicht relevant. Sie testen nur die Teilbarkeit durch 2, 3, 5 und 7, so dass Sie z. 121 = 11 * 11 als Primzahl.

    13 November 2011
    Daniel Fischer
  • Meine Version des Siebs befindet sich unter http://ideone.com/1AP8u Die Funktion, die das Sieben durchführt, wird unten gezeigt. Erläuterungen finden Sie unter meinem Blog . Suchen Sie nach "Primzahlen" im Tag "Themen" unter dem Menüpunkt "Übungen".

     struct node* sieve(int n) {
        int m = (n-1) / 2;
        char b[m/8+1];
        int i=0;
        int p=3;
        struct node* ps = NULL;
        int j;
    
        ps = insert(2, ps);
    
        memset(b,255,sizeof(b));
    
        while (p*p<n) {
            if ISBITSET(b,i) {
                ps = insert(p, ps);
                j = 2*i*i + 6*i + 3;
                while (j < m) {
                    CLEARBIT(b,j);
                    j = j + i + i + 3; } }
            i+=1; p+=2; }
    
        while (i<m) {
            if ISBITSET(b,i) {
                ps = insert(p, ps); }
            i+=1; p+=2; }
    
        return reverse(ps); }
     
    13 November 2011
    Aaron Lee
  • der "Inhaber [1000000];" Array lebt auf dem Stapel ("ist eine automatische Variable"). Ich würde es zumindest statisch machen, da es wiederverwendet werden kann, und es wurde eine Menge Arbeit geleistet (dazu müssten die nicht gesendeten Einträge herausgesucht werden, aber für ein echtes Programm (und eine Funktion) mehr als einmal aufgerufen) wäre ein Gewinn.

    13 November 2011
    Zachary Yates