# Optimierung C++ Primzahlen?



## Defenz0r (2. Februar 2013)

Hallo, 

ich habe mir ein Programm zur Berechnung von Primzahlen geschrieben, leider ist es nicht sehr Performant 
und habe ca. eine Auslastung von 20% bei der Berechnung.

Hier der Code:


```
#include <iostream>
using namespace std;

int main()
{
    int x=0, i=0;
    int anzahl=0,zaehler=0;

    cout<<"Programm zur Berechnung von Primzahlen"<<endl;
    cout<<"Eingabe der Durchlauefe "<<endl;
    cin>>anzahl;

    for(x=2; x<=110000; x++)
    {

    for(int durchlauefe=0; durchlauefe<anzahl; durchlauefe++)

        for(i=2; i<x; i++)
        {
            if(x%i==0) break;
        }

        if(i==x)
        {
             zaehler++;
        }

        if(i==x) cout<<i<<" Ist eine Primzahl. "<<" Nr. "<<zaehler<<endl;
        }


    return 0;

}
```

Die Berechnungszeit steigt Linear an.

Int x ist meine momentan maximale Genauigkeit.


----------



## bingo88 (2. Februar 2013)

Über schnellerer Algorithmen zur Primzahlsuche gibt es genügend Forschungsarbeiten. Aber ich vermute mal, du lastest nur einen Kern aus, daher die geringe Prozentzahl


----------



## Defenz0r (2. Februar 2013)

Keine Ahnung, wie Multithreading funktioniert.

Ich habe gerade ein Skript gefunden, kann mir mal jemand erläutern wie das genau funktionier? :


```
#include "iostream"

int main(int argc, char** argv)
{
   unsigned int prime_nb = 2;
   unsigned long i = 5;
   unsigned int k;
   bool found;
   for(;;)
   {
      found = true;
      for(k = 2; k < i; ++k)
         if(!(i % k))
            found = false;
      if(found)
         ++prime_nb;
      if(prime_nb >= 10001)
         break;
      i += 2; // all even numbers are not prime
   }
   std::cout << i;
   return 0;
}
```

int main(int argc, char** argv)

Zwei Sterne für Char?
++k? heißt das nicht k++?
Warum long?
Warum for( ; ; ) ?? muss da nicht etwas rein?

Bzw. kann jemand dieses Skript etwas kommentieren, Verständnishalber?


Danke


----------



## bingo88 (2. Februar 2013)

Defenz0r schrieb:


> Keine Ahnung, wie Multithreading funktioniert.


 Das ist in so einem Fall auch nicht unbedingt trivial umzusetzen 



Defenz0r schrieb:


> int main(int argc, char** argv)
> 
> Zwei Sterne für Char? *"Zeiger auf einen Zeiger" -> ist das gleiche wie char *argv[]
> ++k? heißt das nicht k++?*
> ...



Ach ja, und es heißt #include <iostream>...


----------



## Defenz0r (2. Februar 2013)

Das Skript ist wie beschrieben nicht von mir.
Du kannst nicht sagen es heißt so oder so.
Es gibt andere Leute die Ihren eigenen Stil haben.


Das ist alles.


----------



## bingo88 (2. Februar 2013)

Defenz0r schrieb:


> Es gibt andere Leute die Ihren eigenen Stil haben.


 Das hat nichts mit Stil zu tun, sondern ist im schlimmsten Fall sogar falsch (compilerabhängig):

#include "bla.h" sucht nach blah.h im AKTUELLEN Verzeichnis
#include <blah.h> sucht in den (eingestellten) Systemverzeichnissen

Es galt jetzt auch nicht dir persönlich, sondern es war einfach eine Feststellung


----------



## Defenz0r (2. Februar 2013)

Achso, ich fühlte mich etwas angegriffen ^^
Ich übe diese Sachen (Project Euler) , weil ich glaube das es mir etwas bringt.
Bin ja in einer Ausbildung zum FIAE, s. Profil.

lg


----------



## bingo88 (2. Februar 2013)

Defenz0r schrieb:


> Achso, ich fühlte mich etwas angegriffen ^^


 Nee, war wirklich nicht so gemeint, sorry!



Defenz0r schrieb:


> Ich übe diese Sachen (Project Euler) , weil ich glaube das es mir etwas bringt.
> Bin ja in einer Ausbildung zum FIAE, s. Profil.


 Ist ja nicht verkehrt, sich so was mal anzusehen, um daraus zu lernen. Wie gesagt, es gibt sicher genug Material dazu (Primfaktorzerlegung wird z. B. bei SSL/RSA verwendet), einfach mal danach im Netz suchen.


----------



## mtheman2011 (3. Februar 2013)

Defenz0r schrieb:


> ++k? heißt das nicht k++?
> ...
> Warum for( ; ; ) ?? muss da nicht etwas rein?
> 
> ...



Beides wird vom Compiler in k =k+1 übersetzt, aber ++k kann unter bestimmten umständen leicht bessere performance bieten. Ist aber relativ irrelevant. Es funktioniert jedenfalls beides.

Und for( ; ; ) ist eine endlosschleife genauso wie while(true). Es gibt einfach keine abbruchbedingung aber mittels break kann die Schleife verlassen werden.


----------



## DMA (3. Februar 2013)

bingo88 schrieb:


> Zwei Sterne für Char? *"Zeiger auf einen Zeiger" -> ist das gleiche wie char *argv[]*


 Nunja, also char** ist nicht das Selbe wie char*[], nur der äußere Effekt ist der Gleiche, die Logik dahinter eine andere.

Ansonsten, Primzahlen zur Laufzeit zu berechnen ist so oder so nicht sonderlich effektiv - zumindest mit den momentanigen Methoden.
Also gerade die Modulo-Operation verschlinkt verhältnismäßig viel Zeit.
Je nachdem wie du den Algorithmus gestaltest, kannst du das Teil aber etwas „effektiver“ gestalten.

Allerdings glaub eich kaum, dass du Primzahlen im großen Stile in deiner FIAE Ausbildung gebrauchen wirst und das Ganze wohl eher eine Übung sein soll(te), damit du mehr vertraut mit der Umsetzung von Problemstellungen bist.


----------



## ofhouse (3. Februar 2013)

mtheman2011 schrieb:


> Beides wird vom Compiler in k =k+1 übersetzt, aber ++k kann unter bestimmten umständen leicht bessere performance bieten. Ist aber relativ irrelevant. Es funktioniert jedenfalls beides.


 
Ich weiß zwar nicht, ob die Performance besser ist (das können nur Nanosekunden sein), aber k++ und ++k machen zwar augenscheinlich dasselbe, sind aber auf keinen Fall gleich.
Bei Rechenausdrücken spielt das ne große Rolle, hier 2 Beispiele:

++k zählt k hoch und rechnet dann den Ausdruck aus und speichert ihn in z.

```
int k = 2;
int z = ++k + 2;
// z = 5; k = 3
```

k++ rechnet erst den Ausdruck aus und speichert ihn in z und zählt danach k hoch.

```
int k = 2;
int z = k++ + 2;
// z = 4; k = 3
```


----------



## mtheman2011 (3. Februar 2013)

Interessant. Is mir noch nie in der Form vorgekommen, weil ich solche Sonderausdrücke immer in Klammern schreibe. Ist aber gut zu wissen. 
Ja hab ja gesagt nicht relevant aber wenn das innerhalb einer schleife passiert und auf Leistungsschwacher Hardware(langsame arm cortex prozessoren zum beispiel) ausgeführt wird kann das Auswirkungen auf das Laufzeitverhalten im Sekundenbereich haben. Kommt aber auch auf die Hardware an.


----------



## DarkMo (4. Februar 2013)

hab die ganze zeit des lesens scho nach nem bsp gesucht ofhouse ^^ ich wusst auch nur, dass ++k "vorher" ausgeführt wird und k++ eben "nachher". aber nen rechten anwendungsfall (vor oder nach was?) kannte ich auch noch ned *g* so sin die studenten: theoretisch profis aber praktisch nullen


----------



## fadade (4. Februar 2013)

DarkMo schrieb:


> so sin die studenten: theoretisch profis aber praktisch nullen


 
Also das sieht bei *mir *ja gaaanz anders aus! 

-> Primzahlensuche kannst du nicht groß optimieren ... man sucht halt ... da kannst du erst bei 2903487907507 anfangen, weil die davor bestimmt schon bekannt sind, man kann Intervalle auf verschiedene Threads aufteilen, aber viel gibts da nicht mehr rauszuholen.


----------



## Olstyle (4. Februar 2013)

Mal eine relativ einfache Variante die mit zunehmender Menge an Zahlen schon mal deutlich schneller ist:
Sieb des Eratosthenes
Irgendwo hab ich auch noch ein entsprechendes C.Programm rumfliegen.


----------



## ofhouse (6. Februar 2013)

Als Motivation, die neueste Primzahl hat 17 millionen Stellen 

Newly-discovered prime number is more than 17 million digits long | The Verge


----------

