problem mit array bei primzahlensuche

volkard

Sone schrieb:

Hier das Sieb des Eratosthenes:

#include <vector>
#include <iostream>

int main()
{
    using namespace std;

    unsigned const N = 1000;

    vector<pair<int, bool> > vec(N - 1); // Platz. Erster Wert ist die Zahl, der zweite bool-Wert gibt an ob diese Zahl noch eine Primzahl sein könnte.

    for( unsigned ct = 0; ct < vec.size(); ++ct )
        vec[ct] = make_pair(ct + 2, true);

    for( unsigned ct = 0; ct < vec.size(); ++ct )
        if( vec[ct].second )
        {
            int value = vec[ct].first;

            for( unsigned multiple = value*value; multiple < vec.size() + 2; multiple += value ) /// Durch alle Vielfachen gehen und diese als Nicht-Prim markieren
                vec[multiple - 2].second = false;
        }

    /// Ausgabe:
    for( unsigned ct = 0; ct < vec.size(); ++ct )
        if( vec[ct].second )
            cout << vec[ct].first << ", ";
}

Ideone: http://ideone.com/JnCKGc

Ist jetzt ganz sicher richtig.

Ich lach mich tot.

vector<bool>

ist fast so gut wie

map<int,bool>

oder Dein

vector<pair<int, bool>>

Schau:

#include <vector>
#include <iostream>

#define first UNUSED

int main()
{
    using namespace std;

    unsigned const N = 1000;

    vector<pair<int, bool> > vec(N - 1); // Platz. Erster Wert ist die Zahl, der zweite bool-Wert gibt an ob diese Zahl noch eine Primzahl sein könnte.

    for( unsigned ct = 0; ct < vec.size(); ++ct )
        vec[ct] = make_pair(ct + 2, true);//Dieses +2 ist dran schuld!

    for( unsigned ct = 0; ct < vec.size(); ++ct )
        if( vec[ct].second )
        {
//            int value = vec[ct].first;
            int value = ct+2;

            for( unsigned multiple = value*value; multiple < vec.size() + 2; multiple += value )
                vec[multiple - 2].second = false;
        }

    /// Ausgabe:
    for( unsigned ct = 0; ct < vec.size(); ++ct )
        if( vec[ct].second )
//            cout << vec[ct].first << ", ";
            cout << ct+2 << ", ";
}

Swordfish

...

ok super, da habe ich noch einiges auszuprobieren und nachzulesen... hab mal überlegt, meine methode sollte O(N^2/ln(N)) sein, das Sieb von E ist ja O(N), hab bei Wikipedia noch das Sieb von Aktin gefunden,das anscheinend O(N/(ln(ln(N))) ist, was ja auch nicht viel besser als O(N) ist^^ gibt es noch einen besseren algorithmus zur primzahlenbestimmung der schneller ist?

volkard

neuhier123d schrieb:

ok super, da habe ich noch einiges auszuprobieren und nachzulesen... hab mal überlegt, meine methode sollte O(N^2/ln(N)) sein, das Sieb von E ist ja O(N), hab bei Wikipedia noch das Sieb von Aktin gefunden,das anscheinend O(N/(ln(ln(N))) ist, was ja auch nicht viel besser als O(N) ist^^ gibt es noch einen besseren algorithmus zur primzahlenbestimmung der schneller ist?

Eigentlich macht das Sieb des E alle anderen Platt.
http://code.google.com/p/primesieve/
Es ist auch recht leicht, es pfiffig zu implementieren.

Mir ist unbekannt, ab wo das Sieb des Atkin schneller wird, aber wohl schon erst bei recht großen Zahlen. Ups, kriegt man es auch so einfach cache-friendly?