Primzahlen

[bwbg]

So, Mittagspause ist fast vorbei und hier ist ein bisschen (funktionierender) Quellcode. Die "kritischen" Stellen sind kommentiert und beziehen sich auf meinen vorangegangenen Beitrag.

Hinweis: Der Algorithmus erhebt nicht den Anspruch besonders performant oder elegant zu sein

// primes.cpp
#include <ios>
#include <iostream>
#include <vector>

typedef unsigned long ULONG;

// ==================================================================
// *** Deklaration Klasse PrimeGenerator und Operatoren ***
class PrimeGenerator
{
    friend std::ostream& operator<<(std::ostream&, const PrimeGenerator&);

private:
    // *** Attribute ***
    std::vector<ULONG> primes;

public:
    // *** Konstruktor ***
    PrimeGenerator()
        : primes()
        { }

    /*** Destruktor, Kopierkonstruktor und Zuweisungsoperator werden
        vom Compiler generiert. ***/

    // *** spezielle Methoden ***
    void generate(ULONG max);
        // Generiert Primzahlen bis zur Obergrenze 'max'

};

std::ostream& operator<<(std::ostream& out, const PrimeGenerator& p);

// ==================================================================
// ==================================================================
using namespace std;

// *** main-Funktion ***
int main(int argc, char** args)
    {
        PrimeGenerator pg;
        pg.generate(10000UL);
        cout << pg << endl;
        return 0;
    }

// ==================================================================
// *** Definition der Klasse PrimeGenerator und Operatoren ***
void PrimeGenerator::generate(ULONG max)
    {
        ULONG n = 2UL;  // Die Iteration startet mit 2

        do {

            // Prüfen, ob n durch eine (vorhandene) Primzahl ohne
            //  Rest teilbar ist.
            bool devideable = false;
            vector<ULONG>::const_iterator iter = primes.begin();

            for(; iter != primes.end() && !devideable; iter++) {
                if(n % (*iter) == 0) devideable = true;
            }

            // Ist n nicht durch eine Primzahl teilbar (for-Schleife
            //  wurde vollständig durchlaufen), so handelt es sich bei
            //  n ebenfalls um eine Primzahl und wird in den 
            //  Primzahlen-vector aufgenommen.
            if(!devideable) primes.push_back(n);

        } while(n++ < max);
    }

ostream& operator<<(ostream& out, const PrimeGenerator& p)
    {
        vector<ULONG>::const_iterator iter = p.primes.begin();
        for(; iter != p.primes.end(); iter++) {
            out << *iter << " ";
        }        
        return out;
    }

Ich hoffe, das hilft Dir ein bisschen, um bei der Thematik durchzublicken.

Grüße aus dem (im Moment sonnigen) Sauerland

Heiko

[Stromberg]

Des mit dem "special_number" war doch nur wegen dem Algorithmus, Sieb des Eratosthenes. (Beitrag von Don06 http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes )
Und da muss man doch alles Vielfachen von 2,3,5 und 7 ausschließen.
....
Aber ich gug mir deinen Code glei au noch an.

MfG
Stromberg

[Don06]

@Stromberg:
Nein nicht nur 2, 3, 5 und 7. Du musst nach und nach die Vielfachen der gefundene Primzahlen wegstreichen.

@Heiko:
Die Methode mit dem Modulo hatten wir schon, das Problem ist, dass so eine Division viel Zeit kostet. Die Methode der Vielfachen ist selbst gegenüber einer stark optimierten Version ca. 10-20 mal schneller. Und dann kann man ja noch optimieren

Ich hab die verschiedenen Methoden mal ausgibig getestet:
PrimePrintResults.xls

Besonders bei der Suche nach großen Primzahlen, dauert die Modulo-Methode einfach zu lange. Allerdings hat sie den Vorteil, dass man sich nicht um Speicher kümmern muss. Die Sieb-Methode kann schon mal ziemlich viel davon in Anspruch nehmen.

Gruß
Don06

[Stromberg]

Ach so, nicht nur mit 2,3,5 und 7 sondern auch immer wieder mit den neu gefundenen Primzahlen.....also das hier ist dann mal mein x ter Versuch des in nen Code reinzupressen, ich hab mir deinen gar nicht so genau angeschaut, weil ich will das selber schaffen nud nicht irgendwie abschreiben.....!

#include <iostream>
using namespace std;

class prime
{
    public:
    prime() {}
    ~prime() {}
    inline bool is_prime(unsigned long &number) const;
    void search_prime(unsigned long &list_end) const;

    private:
    bool array_null(const unsigned long *value,unsigned long &temp) const;

};

bool prime::array_null(const unsigned long *value, unsigned long &temp) const
{
    if (value==0)
    {
        return true;
        temp++;
        array_null(++value,temp);
    }
    else
    {
        return false;
    }
}

bool prime::is_prime(unsigned long &number) const
{
    for (unsigned long i=2;i<number;i++)
    {
        if ((number % i) == 0) return false;
    }
    return true;
}

void prime::search_prime(unsigned long &list_end) const
{
    unsigned long *array=new unsigned long[list_end];
    for (unsigned long i=2;i<=list_end;i++)
    {
        array_null(&array[2-1],i);
        if (is_prime(i))
        {
            for (unsigned long j=2;j*i<=list_end;j++)
            {
                array[j*i-1]=0; //0 = KEINE PRIMZAHL
                //cout << "!\n";
            }
        }
     }

     for (unsigned long i=1;i<=list_end;i++)
     {
         if (array[i-1] != 0) cout << i << endl;
     }
}

int main()
{
    prime test;
    unsigned long a=197;
    test.search_prime(a);

    return 0;
}

Verstehst du den jetzigen Code von mir besser? Also ich erstelle ein Feld, und wenn jetzt z.B. "4" keine Primzahl ist, dann schreib ich "array[3]=0;", oder bei 16 "array[15]=0" und so kann ich das dann gleich immer schnell überprüfen.
Nur das GRÖßTE PROBLEM ist, wenn ich in meine Funktion einen höheren Wert als 196 eintrage, dann steht nur noch "1" u. "2" dran!?! Warum....das verstehe ich überhaupt nicht, warum geht es mit allen Zahlen < 197 aber mit Zahlen > 197 nicht mehr? Da kann doch höchstens bei mir was mit nem Typ nicht stimmen? Aber eigentlich sind alles "unsigned long".....mh des check ich mal gar net, findet jemand den Fehler vll.?

PS: Das "cout" nimmt ja die ganze Schnelligkeit weg, aber das steht bis jetzt nur zu Testzwecken drin. Wenn es mal gehen sollte, dann schmeiß ich des "cout" raus, und schreib alle Primzahlen in ein Feld rein.

MfG
Stromberg

[CStoll]

Die Methode 'array_null()' ist schonmal eine Katastrophe - erstens werden die Teile hinter dem 'return true;' niemals ausgeführt und zweitens ist in diesem Bereich eine Endlosrekursion enthalten. (und was der Sinn der Funktion sein soll, ist auch nicht klar)

[Stromberg]

Stimmt die Methode "array_null" war blödsinn, und viel zu umständlich, ich hab das jetzt mit einer "while Schleife" gelöst (Z. 38-41). (Aber ich hab immer so nen Komplex gegen "while Schleifen", weil ich irgendwo mal gehört habe, das es in einem guten Code nur 1 while Schleife gibt, nämlich die Hauptschleife. Unsinn?)
Aber trotzdem geht meine Funktion nur bis Zahlen < 207, also n bisschen gesteigert hab ich mich schon.....is aber trotzdem merkwürdig!? Wie kann das sein? Ich finde den Fehler einfach nicht, und die Typen stimmen doch auch alle?
Hier der jetzige Code:

#include <iostream>
using namespace std;

class prime
{
    public:
    prime() {}
    ~prime() {}
    inline bool is_prime(unsigned long &number) const;
    void search_prime(unsigned long &list_end) const;

    private:

};

bool prime::is_prime(unsigned long &number) const
{
    for (unsigned long i=2;i<number;i++)
    {
        if ((number % i) == 0) return false;
    }
    return true;
}

void prime::search_prime(unsigned long &list_end) const
{
    unsigned long *array=new unsigned long[list_end];
    for (unsigned long i=2;i<=list_end;i++)
    {

        while(array[i-1]==0)
        {
            i++;
        }

        if (is_prime(i))
        {
            for (unsigned long j=2;j*i<=list_end;j++)
            {
                array[j*i-1]=0; //0 = KEINE PRIMZAHL
            }
        }
     }

     for (unsigned long i=1;i<=list_end;i++)
     {
         if (array[i-1] != 0) cout << i << endl;
     }
}

int main()
{
    prime test;
    unsigned long a=206;
    test.search_prime(a);

    return 0;
}

MfG
Stromberg

[The-Kenny]

Stromberg schrieb:

(Aber ich hab immer so nen Komplex gegen "while Schleifen", weil ich irgendwo mal gehört habe, das es in einem guten Code nur 1 while Schleife gibt, nämlich die Hauptschleife. Unsinn?)

Wie wäre es mit goto anstatt der while-Schleife?

[thordk]

Stromberg schrieb:

Aber ich hab immer so nen Komplex gegen "while Schleifen", weil ich irgendwo mal gehört habe, das es in einem guten Code nur 1 while Schleife gibt, nämlich die Hauptschleife. Unsinn?

das ist sehr großer unsinn hört sich nach nem falsch interpretierten paradigma an.

[OhneName]

Warum versuchst du eigentlich das Problem unbedingt auf objektorientierte Weise zu lösen? Der folgende Code ist zwar C, aber er tut wenigstens was er soll. Das Hauptproblem das er hat ist der extreme Speicherverbrauch. Ein Feld mit 1 Milliarde Elemente brauch nunmal selbst mit dem Datentypen char 1GB Platz.

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[])
{
    /* obere Grenze bis zu der die Primzahlen berechnet werden einlesen */
    unsigned long n = 0;
    printf("Bis zu welcher Zahl wollen Sie die Primzahlen berechnen: ");
    scanf("%lu", &n);

    /* Feld mit passender Größe anlegen und alle Werte auf 1 setzen.
    1 bedeutet die Zahl ist eine Primzahl, 0 bedeutet nein */
    unsigned char *sieb = malloc(n);
    memset(sieb, 1, n);

    /* alle geraden Zahlen größer 2 sind keine Primzahlen */
    unsigned long i = 0;
    for(i = 4; i < n; i = i + 2)
    {
        sieb[i] = 0;
    }

    /* 0 und 1 sind keine Primzahlen */
    sieb[0] = 0;
    sieb[1] = 0;

    /* der eigentliche Sieb. Für jede ungerade Zahl i zwischen 3 und Wurzel n
    werden alle Vielfachen aus dem Sieb gestrichen. Die Vielfachen von bereits
    gestrichenen Zahlen werden nicht beachtet, da sie bereits gestrichen wurden. */
    unsigned long j = 0;
    for(i = 3; i < sqrt(n); i = i + 2)
    {
        if(sieb[i] == 1)
        {
            for(j = 2 * i; j < n; j = j + i)
            {
                sieb[j] = 0;
            }
        }
    }

    /* alle Primzahlen ausgeben */
    for(i = 2; i < n; ++i)
    {
        if(sieb[i] == 1)
        {
            printf("%8lu", i);
        }
    }

    /* Speicher freigeben */
    free(sieb);
    return 0;
}

[Badestrand]

OhneName schrieb:

Ein Feld mit 1 Milliarde Elemente brauch nunmal selbst mit dem Datentypen char 1GB Platz.

Wenn du mit Bits arbeitest und von Anfang an nur jede zweite Zahl (die ungeraden) einbeziehst, brauchst du nur 62 MB

edit: Mit Bits ist es dann allerdings ein wenig langsamer...

edit2: Mir war so danach, ich hab deine (OhneNamen) Version einfach mal umgeschrieben, sieht aber nicht sonderlich elegant aus
Könnte man bestimmt noch optimieren, aber immerhin ist sie recht schnell und der Speicherverbrauch recht gering.

bool GetBit( unsigned char* ptr, unsigned long idx )
{
	if ( idx%2 == 0 )
		return false;
	idx /= 2;
	return (ptr[idx/8] >> (idx%8)) & 1;
}

void SetBit( unsigned char* ptr, unsigned long idx, bool val )
{
	if ( idx%2 == 0 )
		return;
	idx /= 2;

	if ( val )
		ptr[idx/8] |= 1 << (idx%8);
	else
		ptr[idx/8] &= ~( 1 << (idx%8) );
}

void printPrimes1(uint n, bool print)
{
    /* Feld mit passender Größe anlegen und alle Werte auf 1 setzen.
    1 bedeutet die Zahl ist eine Primzahl, 0 bedeutet nein */
    unsigned char *sieb = (unsigned char*)malloc( n/16 + 1 );
    memset(sieb, 0xff, n/16 + 1);

    /* 1 ist keine Primzahl */
	SetBit( sieb, 1, 0 );

    /* das eigentliche Sieb. Für jede ungerade Zahl i zwischen 3 und Wurzel n
    werden alle Vielfachen aus dem Sieb gestrichen. Die Vielfachen von bereits
    gestrichenen Zahlen werden nicht beachtet, da sie bereits gestrichen wurden. */
    for( unsigned long i=3, sr=sqrt((double)n); i<sr; i+=2 )
		if ( GetBit( sieb, i ) == 1 )
            for( unsigned long j=2*i; j<n; j+=i )
				SetBit( sieb, j, 0 );

    /* alle Primzahlen ausgeben, inklusive der 2 */
	if ( print )
	{
		printf( "%8lu", 2 );
	    for ( unsigned long i=2; i<n; i++ )
			if ( GetBit( sieb, i ) == 1 )
	            printf("%8lu", i );
	}

    /* Speicher freigeben */
    free(sieb);
}

edit: 1300

edit: Da wir im C++-Forum sind, sollte man natürlich cout und BitSet benutzen (@me)

[CStoll]

@Stromberg: Vielleicht solltest du mal im Debugger verfolgen, was da eigentlich passiert. (mir fällt auf Anhieb nur auf, daß dein Sieb mit 0 initialisiert wird, also alle Zahlen von vornherein als Nicht-Primzahl einstuft)

(Randfrage: Hat es einen besonderen Grund, daß du die Parameter an is_prime() und search_prime() per Referenz übergibst?)

@Badestrand: Ja, bitset<> wäre eine Möglichkeit, aber mit einem entscheidenden Nachteil - du mußt die Größe bereits beim Compilen festsetzen. Da die Größe dynamisch sein soll, passt wohl eher vector<bool>.