programm zum Sieb des Eratosthenes...bitte um verbesserung/hilfe mit nem kleinen problem

[chris' 1]

huhu,

ich hab aus langeweile mal n programm zur primzahlberechnung mit dem Sieb des Eratosthenes geschrieben. könnte jemand das kleine programm mal in richtung performance + verbesserungen überprüfen? wäre dem sehr dankbar!

hier der code:

// Primzahlberechnung mit dem Sieb des Eratosthenes
// Filename: prime.cpp

#include <iostream>
#include <math.h>

using namespace std;

// prototypes
void initPrimes  (const unsigned int PrimeMax, bool* p_bPrimes);
void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes);
void printPrimes (const unsigned int PrimeMax, const bool* p_bPrimes);

// main
int main()
{
    // variables
    bool* p_bPrimes = NULL;     // Pointer auf das spätere bool-Array für die Primzahlen
    unsigned int PrimeMax;      // größte Zahl, die auf Primalität geprüft werden soll

    // User nach PrimeMax fragen
    cout << "Groesste Zahl eingeben, die auf Primalitaet geprueft werden soll: ";
    cin >> PrimeMax;

    // Speicher auf dem Heap reservieren
    p_bPrimes = new bool[PrimeMax];

    // initialisieren, heraus"sieben" und ausgeben
    initPrimes(PrimeMax, p_bPrimes);

    checkPrimes(PrimeMax, p_bPrimes);

    printPrimes(PrimeMax, p_bPrimes);

    // reservierten Speicher freigeben
    delete[] p_bPrimes;
    p_bPrimes = NULL;

    return 0;

} // main

// functions

// initPrimes
// alle Zahlen zwischen 2 und PrimeMax als Primzahlen initialisieren
void initPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int i = 2; i <= PrimeMax; ++i)
    {
        p_bPrimes[i] = true;
    }

} // initPrimes

// checkPrimes
// Non-Primzahlen heraus"sieben"
void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int i = 2; i <= sqrt(PrimeMax); ++i)
    {
        if (p_bPrimes[i])
        {
            for (int j = i * i; j <= PrimeMax; ++j)
            {
                if (j % i == 0)
                {
                    p_bPrimes[j] = false;
                }
            }
        }
    }

} // checkPrimes

// printPrimes
// Primzahlen in der Konsole ausgeben
void printPrimes (const unsigned int PrimeMax, const bool* p_bPrimes)
{
    for (int i = 2; i <= PrimeMax; ++i)
    {
        if (p_bPrimes[i])
        {
            cout << i << endl;
        }
    }

} // printPrimes

was ich außerdem noch wissen wollte: wie übergebe ich der funktion "printPrimes" das array als referenz?
wenn ich es so mache:

// printPrimes
// Primzahlen in der Konsole ausgeben
void printPrimes (const unsigned int PrimeMax, const bool& r_bPrimes)
{
    for (int i = 2; i <= PrimeMax; ++i)
    {
        if (r_bPrimes[i])
        {
            cout << i << endl;
        }
    }

} // printPrimes

bekomme ich folgenden compilerfehler:

invalid types `const bool[int]' for array subscript

gruß,

chris

[volkard]

// Primzahlberechnung mit dem Sieb des Eratosthenes
// Filename: prime.cpp //komischer kommentar. 

#include <iostream>
#include <math.h>

using namespace std;

// prototypes 
//schreib keine prototypen mehr. schreib einbfach die funktionen vor die main. 
void initPrimes  (const unsigned int PrimeMax, bool* p_bPrimes);
//der int muß nicht const sein, ist doch by value übergeben. 
void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes);
void printPrimes (const unsigned int PrimeMax, const bool* p_bPrimes);

// main
int main()
{
    // variables
//ganz schlecht. mach die variablen so spät wie möglich!
    bool* p_bPrimes = NULL;     // Pointer auf das spätere bool-Array für die Primzahlen
    unsigned int PrimeMax;      // größte Zahl, die auf Primalität geprüft werden soll

    // User nach PrimeMax fragen
    cout << "Groesste Zahl eingeben, die auf Primalitaet geprueft werden soll: ";
    cin >> PrimeMax;

    // Speicher auf dem Heap reservieren
    p_bPrimes = new bool[PrimeMax];
//also hier: bool* p_bPrimes = new bool[PrimeMax];
    // initialisieren, heraus"sieben" und ausgeben
    initPrimes(PrimeMax, p_bPrimes);

    checkPrimes(PrimeMax, p_bPrimes);

    printPrimes(PrimeMax, p_bPrimes);

    // reservierten Speicher freigeben
    delete[] p_bPrimes;
    p_bPrimes = NULL;//unnötig. 

    return 0;

} // main

// functions

// initPrimes
// alle Zahlen zwischen 2 und PrimeMax als Primzahlen initialisieren
void initPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int i = 2; i <= PrimeMax; ++i)
//äh. <= PrimeMax? 
//passt nicht zu new bool[PrimeMax];
//greifst auf ein element zu viel zu
    {
        p_bPrimes[i] = true;
    }

} // initPrimes

// checkPrimes
// Non-Primzahlen heraus"sieben"
void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int i = 2; i <= sqrt(PrimeMax); ++i)
//vielleicht besser 
//    int endi=sqrt(PrimeMax);
//    for (int i = 2; i <= endi; ++i)
    {
        if (p_bPrimes[i])
        {
            for (int j = i * i; j <= PrimeMax; ++j)
//            for (int j = i * i; j <= PrimeMax; j+=2)
//allerdings die geraden zahlen extra behandeln. 
            {
                if (j % i == 0)
                {
                    p_bPrimes[j] = false;
//                    if(p_bPrimes[j]) p_bPrimes[j] = false;
//ist lustigerweise schneller, weil du seltener schreibst, 
//schreiben ist teuer als lesen
                }
            }
        }
    }

} // checkPrimes

// printPrimes
// Primzahlen in der Konsole ausgeben
void printPrimes (const unsigned int PrimeMax, const bool* p_bPrimes)
{
//cout<<2<<'\n';
//    for (int i = 3; i <= PrimeMax; i+=2)
    for (int i = 3; i <= PrimeMax; i++)
    {
        if (p_bPrimes[i])
        {
            cout << i << endl;
        }
    }

} // printPrimes

was ich außerdem noch wissen wollte: wie übergebe ich der funktion "printPrimes" das array als referenz?

arrays übergeben sich von alleine per referenz. sozusagen.
aber du hast ja gar kein echtes array, sondern einen zeiger auf freispeicher. dann mußte auch diesen zeiger übergeben, wie du es gemacht hast.

[camper]

volkard schrieb:

// checkPrimes
// Non-Primzahlen heraus"sieben"
void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int i = 2; i <= sqrt(PrimeMax); ++i)
//vielleicht besser 
//    int endi=sqrt(PrimeMax);
//    for (int i = 2; i <= endi; ++i)
    {
        if (p_bPrimes[i])
        {
            for (int j = i * i; j <= PrimeMax; ++j)
//            for (int j = i * i; j <= PrimeMax; j+=2)
//allerdings die geraden zahlen extra behandeln. 
            {
                if (j % i == 0)
                {
                    p_bPrimes[j] = false;
//                    if(p_bPrimes[j]) p_bPrimes[j] = false;
//ist lustigerweise schneller, weil du seltener schreibst, 
//schreiben ist teuer als lesen
                }
            }
        }
    }
    
} // checkPrimes

das ist ein scherz oder ? die sache mit dem schreiben kann richtig sein, es käme auf den exakten code an, den der compiler darausmacht, aber es ist keine prinzipielle verbesserung. auf jedenfall müsste aber klar sein, dass

if (j % i == 0)

völliger unfug ist...

void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int j = 2; j <= PrimeMax; j+=2 )
        p_bPrimes[j] = false;
    for (int endi=sqrt(PrimeMax), i = 3; i <= endi; i+=2)
    {
        if (p_bPrimes[i])
        {
            for (int j = i * i; j <= PrimeMax; j += 2*i)
            {
                p_bPrimes[j] = false;
            }
        }
    }
}

[volkard]

das mit dem % hab ich gar nicht zur kenntnis genommen, weil das zu ausgefallen war.
natürlich j += 2*i und kein %, genau wie du sagst.

[chris' 1]

hi!
danke für eure verbesserungen.
weshalb nimmt man besser kein modulo?langsamer oder? weil funktioniert hats.
ich hab mal umgebaut, wie ihr es empfohlen und ich es sinnvoll gehalten hab(t):

// Programm zur Primzahlberechnung mit dem Sieb des Eratosthenes

#include <iostream>
#include <math.h>

using namespace std;

// functions

// initPrimes
// alle Zahlen zwischen 2 und PrimeMax als Primzahlen initialisieren
void initPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    for (int i = 2; i <= PrimeMax; ++i)
    {
        p_bPrimes[i] = true;
    }

} // initPrimes

// checkPrimes
// Non-Primzahlen heraus"sieben"
void checkPrimes (const unsigned int PrimeMax, bool* p_bPrimes)
{
    // alle geraden Zahlen außer '2' sind keine Primzahlen
    for (int j = 2; j <= PrimeMax; j += 2)
    {
        p_bPrimes[j] = false;
    }

    // alle Vielfachen ungerader Primzahlen sind keine Primzahlen
    for (int endi = static_cast<int> (sqrt(PrimeMax)), i = 3; i <= endi; i += 2)
    {
        if (p_bPrimes[i])
        {
            for (int j = i * i; j <= PrimeMax; j += 2 * i)
            {
                p_bPrimes[j] = false;
            }
        }
    }
} // checkPrimes

// printPrimes
// Primzahlen in der Konsole ausgeben
void printPrimes (const unsigned int PrimeMax, const bool* p_bPrimes)
{
    cout << "2\n";
    for (int i = 3; i <= PrimeMax; i += 2)
    {
        if (p_bPrimes[i])
        {
            cout << i << endl;
        }
    }

} // printPrimes

// main
int main()
{    
    unsigned int PrimeMax;      // größte Zahl, die auf Primalität geprüft werden soll
    // User nach PrimeMax fragen
    cout << "Groesste Zahl eingeben, die auf Primalitaet geprueft werden soll: ";
    cin >> PrimeMax;

    // Speicher für bool-Array auf dem Heap reservieren
    bool* p_bPrimes = new bool[PrimeMax + 1];

    // initialisieren, heraus"sieben" und ausgeben
    initPrimes(PrimeMax, p_bPrimes);

    checkPrimes(PrimeMax, p_bPrimes);

    printPrimes(PrimeMax, p_bPrimes);

    // reservierten Speicher freigeben
    delete[] p_bPrimes;

    return 0;

} // main

wenn ich nun

bool* p_bPrimes = new bool[PrimeMax + 1];

so mit + 1 erzeuge, dann kann ich die schleife mit <= ruhig so stehen lassen oder? ansonsten tritt nämlich der fehler auf, das wenn der user bspw 103 eingibt, und die schleife nur mit < gemacht wird, wird 103 nicht als primzahl ausgegeben da ja nicht drauf zugegriffen werden könnte...stimmt so oder?

gruß,

chris

[volkard]

chris' schrieb:

hi!
danke für eure verbesserungen.
weshalb nimmt man besser kein modulo?langsamer oder?

ja.

[CStoll]

chris' schrieb:

weshalb nimmt man besser kein modulo?langsamer oder? weil funktioniert hats.
ich hab mal umgebaut, wie ihr es empfohlen und ich es sinnvoll gehalten hab(t):

Kurz: ja
Lang: Jeder Schleifendurchlauf braucht Zeit. Und wenn du deinen Zähler bei jedem Schritt um 2*i erhöhst, verringerst du damit effektiv die Anzahl deiner Schleifendurchläufe.

wenn ich nun

bool* p_bPrimes = new bool[PrimeMax + 1];

so mit + 1 erzeuge, dann kann ich die schleife mit <= ruhig so stehen lassen oder? ansonsten tritt nämlich der fehler auf, das wenn der user bspw 103 eingibt, und die schleife nur mit < gemacht wird, wird 103 nicht als primzahl ausgegeben da ja nicht drauf zugegriffen werden könnte...stimmt so oder?

Ja, dann ist das <= anwendbar (C/C++-Arrays werden ab 0 gezählt, deshalb hat das letzte Element den Index größe-1).

[schorsch code]

Da wir schon beim Optimieren sind: Ich würde das mit dem Sieb nicht ganz so ernst nehmen und den Speicherverbrauch hinsichtlich der Lücken im Array optimieren. Das kann man erreichen, indem man direkt die Primzahlen anstatt der Prädikate speichert und überprüft, ob eine Zahl ein Vielfaches davon ist:

#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>

using namespace std;

unsigned long *createPrimes(unsigned int n)
{
    if(n==0)
        return 0;

    int i=1;
    unsigned long test = 3, limit;
    unsigned long *primes = new unsigned long[n];
    bool isPrime;

    primes[0]=2;

    while(i!=n)
    {
        isPrime = true;       
        limit = static_cast<unsigned long>(sqrt(static_cast<long double>(test)));

        //prüfen, ob es ein Vielfaches einer ungeraden Primzahl ist
        for(int j=1; j<i; ++j)
            if(test%primes[j] == 0)
            {
                isPrime=false;
                break;
            }
            else if(primes[j]>limit)
                break;

        if(isPrime)
            primes[i++]=test;

        test += 2;//nur ungerade Zahlen prüfen
    }

    return primes;
}

void pushPrimesUntil(unsigned int max, vector<unsigned long> &result)
{
    if(max<2)
        return;

    unsigned long test = 3, limit;
    bool isPrime;

    result.push_back(2);

    while(test<=max)
    {
        isPrime = true;       
        limit = static_cast<unsigned long>(sqrt(static_cast<long double>(test)));

        //prüfen, ob es ein Vielfaches einer ungeraden Primzahl ist
        for(int j=1; j<result.size(); ++j)
            if(test%result[j] == 0)
            {
                isPrime=false;
                break;
            }
            else if(result[j]>limit)
                break;

        if(isPrime)
            result.push_back(test);

        test += 2;//nur ungerade Zahlen prüfen
    }   
}

template<typename T>
void printLines(T *array, int count)
{
    copy(array, array+count, ostream_iterator<T>(cout, "\n"));
}

template<typename TContainer>
void printLines(const TContainer &container)
{
    copy(container.begin(), container.end(), ostream_iterator<typename TContainer::value_type>(cout, "\n"));
}

int main()
{   
    const int N=100;
    unsigned long *primes = createPrimes(N);
    cout << "Die ersten " << N << " Primzahlen:" << endl;
    printLines(primes, N);
    delete[] primes;   

    cout << endl;

    vector<unsigned long> test;
    cout << "Die Primzahlen bis " << N << ":" << endl;
    pushPrimesUntil(N,test);
    printLines(test);   

    cin.get();
}

[CStoll]

@schorch: Das ist zwar ein nettes Programm zur Erzeugung von Primzahlen, aber nicht mehr das Sieb des Eratosthenes. (und irgendwas sagt mir, daß das eher langsamer ist als die ursprüngliche Variante)

[schorsch code]

@CStoll: Du hast wohl Recht. Dachte beim Sieb des Eratosthenes geht es trotz des Namens eher um die Tatsache, dass eine Primzahl kein Vielfaches einer anderen Primzahl sein darf, als das tatsächliche Wegstreichen der Vielfachen. Was die Geschwindigkeit angeht, müsste zumindest das Ausgeben schneller sein