Primzahlen

Don06

Ja klar.
1. Dein Programm ist falsch! Eine Zahl wird als Primzahl berehnet, obwohl sie keine ist! Siehe Definition von Primzahl.

2. EDIT: naja, egal.

3. kann man eine bestimmte Gruppe von Zahlen bereits im Vorhinein ausschließen (bis auf ein Zahl ;))

usw.

P.S.: Ich wäre ein bisschen anders an die Sache herangegangen, aber so gehts ja auch

Gruß
Don06

Th

Ja, denk einfach mal nach, welche Zahlen überhaupt Primzahlen sein können. Tipp: du prüfst jede Zahl, ob sie ein Primzahl ist.
Außerdem brauchst du die möglichen Teiler nicht alle zu durchlaufen.
Es reicht, wenn du bis zur Hälte der möglichen Primzahl hochzählst und auf Primzahl testest (Beispiel: 23, dann ist die Zahl auf keinen Fall durch 12 und höher teilbar).

Auch solltest du evtl. eine Abbruchbedingung bzgl. des Datentyps 'long' einbauen (unsigned long wäre sogar besser).

Wenn du wirklich ein effizientes Primzahlsuchprogramm schreiben willst - besonders für große Zahlen - dann mußt du dich erst ein bißchen mit Primzahl-Mathematik auseinandersetzen.

mad_martin

AFAIK reicht es sogar, nur bis zur Wurzel von x zu prüfen.

Th

Ja, das mit der Wurzel stimmt, aber ich weiß nicht, ob der Threadersteller dies so einfach begreift. Daher habe ich ihm erstmal den Tipp mit der Hälfte gegeben und dann auf die umfangreiche Theorie verwiesen...

moagnus

Hm, das versteh ich jetzt aber auch nicht.
Bsp.: 9 ist prim? -> Prüfen bis 9^(1/2) = 3 -> 2 und 3 sind prim, 9 aber nicht.

Don06

Du musst dann nur bis sqrt(9) nach Teilern suchen! also nur 1, 2 und 3 überprüfen. Bei 3 wirst du fündig und weisst, dass es keine Primzahl ist.

Gruß
Don06

moagnus

Ups, sehr peinlich

Don06

Nur als Tipp die übliche Herangehensweise an das Problem (Teiler-Suche) ist ziemlich lahm. Abhilfe schafft hier eine interessante Methode von Erathosthenes. Er entwickelte vor 2000 Jahren oder so das Sieb des Eratosthenes. Die Methode ist verdammt schnell, benötigt aber dementsprechend auch mehr Speicher.

Bei einer Suche bis zu 20. Mio braucht er auf meinem Rechner nur 2,25s, aber ca. 2,4MB SPeicher mehr als die übliche Methode). Die übliche Methode braucht hingegen ca 50s und selbst die von mir eigenhändig optimierte bruacht noch ca. 26s.
Dazu mal ein kleiner Screenshot meiner Testreihe.

Da die Methode des Siebs des Eratosthenes noch nicht optimiert ist, lässt sich da bestimmt noch ein bisschen rausholen.

Gruß
Don06

Stromberg

Ich hab versucht das mit den Primzahlen jetzt mit dem "Sieb des Eratosthenes" zu lösen, aber irgendwas stimmt an meinem Code nicht. Ich hab n vorhin mal getestet, und der hat nur "merkwürdige" Ergebnisse ausgespuckt.

#include <iostream>
using namespace std;

enum NUMBER {N_a=2,N_b=3,N_c=5,N_d=7};

class Prime
{
    public:
    explicit Prime();
    ~Prime();
    void SearchPrime(const unsigned long &value);
    inline const unsigned long * get_PrimeNumber() const {return m_PrimeNumber;}

    private:
    unsigned long *m_PrimeNumber;

};

Prime::Prime()
:m_PrimeNumber(NULL)
{

}

Prime::~Prime()
{
    delete m_PrimeNumber;
}

void Prime::SearchPrime(const unsigned long &value)
{
    unsigned long temp=value;
    NUMBER special_number;
    unsigned long *array=new unsigned long[value];

    for (int j=0;j<4;j++)
    {
        switch(j)
        {
            case 0:
            special_number=N_a;
            break;
            case 1:
            special_number=N_b;
            break;
            case 2:
            special_number=N_c;
            break;
            case 3:
            special_number=N_d;
            break;
        }

        for (unsigned long i=1;temp<2;i++)
        {
            array[i*special_number]=true;
            temp=temp-special_number;
        }

        temp=value;

    }

    unsigned long counter=0;;

    for(unsigned long i=1;i<value;i++)
    {
        if (array[i] != true)
        {
            counter++;
            //cout << array[i] << "\n";  <--TESTEN OBS GEHT
        }
    }

    m_PrimeNumber=new unsigned long[counter];

    for(unsigned long i=1;i<value;i++)
    {
        if (array[i] != true) m_PrimeNumber[i]=array[i];
    }

    delete array;
}

MfG
Stromberg

Don06

Ähm, deinen Code hab ich jetzt nich so gecheckt
Aber naja, die Technik eignet sich sowieso erst, wenn man im Voraus weiß, bis zu welcher Nummer gesucht werden soll.
Ausserdem solltest du besser std::vector<bool> zum speichern das Primstatus verwenden. sonst verchwendest du bei großen Zahlen zu viel Platz. (Verhältnis 1:8).
Du kannst dir ja mal meine nicht optimierte Version des Algorithmus ansehen:

typedef unsigned long uint;

void printPrimes(uint max)
{
	std::vector<bool> isPrimeArray(max + 1, true);
	isPrimeArray[0] = false;
	isPrimeArray[1] = false;

	uint factor = 2;
	uint squareRoot = static_cast <uint> 
		(sqrt(static_cast <double> (max)) + 0.5);
	while (factor <= squareRoot)
	{
		uint not_a_prime = factor + factor;
		while (not_a_prime <= max)
		{
			isPrimeArray[not_a_prime] = false;
			not_a_prime += factor;
		}

		++factor;
		while (!isPrimeArray[factor])
			++factor;
	}

	for (uint i = 0; i <= max; ++i)
		if (isPrimeArray[i])
			printf("%lu\n", i);
}

Du solltest die Ausgabe, aber in eine Date umleiten, da sonst die meiste Zeit mit der Konsolenausgabe verschwendet würde.

Also zB so aus der Konsole aufrufen:

PrintPrimes > primes.txt

Gruß
Don06

Stromberg

Ich hab meinen Code jetzt nochmal überarbeitet, und er funktioniert. Nur ist das blöde, wenn man in meiner Funktion einen größere Zahl als 198 eingibt.....dann gibt er in der Konsole nur noch "1" aus!? Ich verstehe das nicht...an was kann das liegen...und "198", das hat doch mit nichts nen zusammenhang? Also ich check das nicht....!?! Wenn euch was ins Auge sticht, oder die Zahl "198" euch was sagt fänd ichs Klasse.

#include <iostream>
using namespace std;

class Prime
{
    public:
    explicit Prime();
    ~Prime();
    void SearchPrime(const unsigned long &value);
    inline const unsigned long * get_PrimeNumber() const {return m_PrimeNumber;}
    inline unsigned long get_counter() const {return m_counter;}

    private:
    unsigned long *m_PrimeNumber;
    unsigned long m_counter;

};

Prime::Prime()
:m_PrimeNumber(NULL),m_counter(0)
{

}

Prime::~Prime()
{
    delete []m_PrimeNumber;
}

void Prime::SearchPrime(const unsigned long &value)
{
    unsigned long *array=new unsigned long[value];
    unsigned short special_number=0;

    for (short j=0;j<4;j++)
    {
        switch (j)
        {
            case 0:
            special_number=2;
            break;
            case 1:
            special_number=3;
            break;
            case 2:
            special_number=5;
            break;
            case 3:
            special_number=7;
            break;
        }

        for (unsigned long i=1;(special_number*i)<=value;i++)
        {
            array[special_number*i]=0;
        }
    }

    for (unsigned long i=1;i<value;i++)
    {
        if (array[i] != 0) m_counter++;
    }

    m_PrimeNumber=new unsigned long[m_counter];
    unsigned long x=0;

    for (unsigned long i=1;i<value;i++)
    {
        if (array[i] != 0)
        {
            m_PrimeNumber[x]=i;
            x++;
        }
    }

    delete []array;
}

int main()
{
    Prime test;
    test.SearchPrime(10000);
    const unsigned long *temp=test.get_PrimeNumber();
    for (unsigned long i=0;i<test.get_counter();i++)
    {
        cout << temp[i] << "\n";
    }

    return 0;
}

@Don06
Ich schau mir jetzt mal deinen Code an, ich glaub meiner is im Vergleich zu deinem ziemlich hässlich :(...aber gut wenigstens funktioniert mein Code. (bis "198" :D)

MfG
Stromberg

bwbg

Ich weiß immer noch nicht, was du mit Deinen special_numbers anstellen willst.

Für Primzahlen gilt:

Eine Zahl aus der Menge der natürlichen Zahlen (N) größer 1 ist genau dann eine Primzahl, wenn sie durch 1 und sich selbst ohne Rest teilbar ist.

Des weiteren gilt:

Jede Zahl aus der Menge N größer 1 lässt sich als Produkt von Primzahlen darstellen.

Daraus folgt, dass eine natürliche Zahl q größer 1, welche nicht durch eine Primzahl kleiner q ohne Rest teilbar ist, eine Primzahl ist.

Bsp:
2 ist nicht durch eine Primzahl teilbar -> Primzahl
3 ist nicht durch eine Primtahl teilbar -> eine Primzahl
4 ist durch 2 teilbar: 2 x 2 = 4 -> keine Primzahl
5 ist nicht durch eine Primzahl teilbar -> Primzahl
6 ist durch 2 und 3 teilbar: 2 x 3 = 6 -> keine Primzahl
7 ist nicht durch eine Primzahl teilbar -> Primzahl
8 ist durch 2 teilbar: 2 x 2 x 2 = 8 -> keine Primzahl
9 ist durch 3 teilbar: 3 x 3 = 9 -> keine Primzahl
10 ist durch 2 und 5 teilbar: 2 x 5 = 10 -> keine Primzahl
...
100 ist durch 2 und 5 teilbar: 2 x 2 x 5 x 5 = 100 -> keine Primzahl
...

Das Thema reizt mich nun auch und ich versuche das ganze mal zu implementieren.

Grüße...

Heiko

pumuckl

Wer sich mal mit einer lustigen Spielerei auseinandersetzen will, die mit dem Thema zu tun hat: im Buch C++ Templates | ISBN: 0201734842 gibts ein codebeispiel wo mittels Templates Primzahlen gefunden werden. Der Clou: Das Programm hat keine Laufzeit, die Primzahlen werden bereits beim Compilieren als Warnmeldungen ausgegeben!

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?