Primzahlenberechnung effektiver machen

[dead_orc]

Ich habe mir als Übung ein kleines Programm geschrieben, dass Primzahlen berechnet, nach 50000 überprüften Zahlen aufhört und den Status in Dateien speichert. Ich habe das Programm schon versucht so effizient wie möglich zu machen, doch bin ich mir sicher, dass die Leute, die was davon verstehen, noch mehr Möglichkeiten finden, das Programm zu verbessern. Hier der Sourcecode:

Code:

#include <iostream.h>
#include <fstream.h>

int main()
{
    int x;
    int y;
    int new_int;
    int old_int;
    int a;
    bool z = true;
    int yn;
    fstream state("state.txt", ios::in | ios::out);
    if(!state)
    {
              x = 1000;
    }
    else
    {
              state >> x;
    }
    if(x < 1000)
    {
         x = 10;
    }
    int end = x + 50000;
    cout << "Working..." << endl;
    for(int y = x; y <= end; y++)
    {
            if((y%2) != 0 && (y%3) != 0 && (y%5) != 0 && (y%7) != 0)
            {
                     z = true;
                     for(a = 11; a <= y / 2 && z == true; a+=2)
                     {
                           if((y%a) == 0)
                           {
                                    z = false;
                           }
                     }
                     if(z == true)
                     {
                           new_int = y;
                     }
            }
    }
    cout << new_int << endl;
    state.clear();
    state.seekg( 0, ios::beg );
    state << end;
    fstream lpz("lpz.txt", ios::in | ios::out);
    lpz >> old_int;
    if(new_int > old_int || !lpz)
    {
               lpz.clear();
               lpz.seekg( 0, ios::beg );
               lpz << new_int;
    }
}

PS: Ich wäre auch für Stilverbesserung dankbar, da ich mir gleich einen ordentlichen Programmierstil angewöhnen möchte

[Rolus]

Ich habe auch mal so ein Programm geschrieben. Allerdings hat meins alle Primzahlen aus einem bestimmten Zahlenabschnitt rausgesucht und in eine Datei geschrieben. Bei deinem Programm wird aber anscheinden immer nur eine Zahl rausgeschrieben. Und dein Überprüfvorgang ist auch nicht sehr schnell. Ich stelle mal mein Programm hierhin:

Code:

#include <windows.h>
#include <iostream.h>
#include <conio.h>

int main ()
{
    int anfang = 99999999 ;  
    int ende = 100001000;
    int b = 1 ;         
    int c = 0 ;         
    int tmp = 0;
    char	String[1024];
    
    FILE* LogFile = NULL;
    LogFile = fopen("Log.html", "wc");
    LogFile = fopen("Log.html", "w+t");
    fprintf(LogFile, "<h2>Log-File</h2>" );
    fclose(LogFile);
        
while (anfang < ende)  
{
 ++anfang;
 ++anfang;           
                                                  
 b = 1 ;
 tmp = b * b;                 
 while (tmp < anfang)            
 {
  if (anfang % b == 0)       
  { 
    ++c ;          
  }
  ++b;
  tmp = b * b;
  if(c<1)
  {
   break;
  }
 }
 if (c == 1)        
 {
    wsprintf(String,"%d",anfang);
    cout << String << "\n";     
	LogFile = fopen("Log.html", "a");
	fprintf(LogFile, String );
	fprintf(LogFile, "<br>" );
	fclose(LogFile);
 }
 c = 0;            
}   
}

Von anfang bis ende wird nach Primzahlen gesucht und in die Datei Log.html geschrieben. Allerdings dürfen für anfang nur ungerade Zahlen verwendet werden. Wenn dein Programm mal alle Zahlen aufschreiben würde, könntest du ja mal einen Schnelligkeitstest machen.

freundliche Grüße, Rolus

[Feenstaub]

Eure Ausführungen haben mich an alte, längst vergessene Zeiten und das Sieb des Eratosthenes erinnert - wohl einer der ersten Algorithmen, mit denen sich ein(e) angehende(r) Programmierer(in) herumärgern muss. ^^

@getöteter_ork:

• Die Idee, eine erste Kurzschlussreaktion mit 2,3,5 und 7 zu machen, finde ich gut.
• Die Bedingung "a <= y / 2" in der For-Schleife solltest du zu "a <= sqrt(y)" abändern, sofern es sich um die Abbruchbedingung handelt, bis zu der die Überprüfung laufen soll.
• Deinem Quelltext nach dürftest du eigentlich keine Liste von Primzahlen herausbekommen, sondern eher die letzte grösste Primzahl bis zur geforderten Grenze.

@Rolus:

• Schöne Idee, dass mit der HTML-File.
• Die Break-Anweisung für "c<1" soll sicher gelten für "c>1". Ansonsten geht die Schleife ja immer bis zum letzten "tmp" durch, also immer bis zur Wurzel der Ausgangszahl.

Generelle Anmerkungen:

• Bei beiden Versionen fehlt mir eine Idee, um die vorhergehenden Ergebnisse mit einfliessen zu lassen. Für jede zu testende Zahl werden sämtliche Berechnungen immer wieder von vorn gestartet. Das ist sicher hinreichend für das Problem, eine einzelne Zahl auf Primzahl zu testen. Aber bei grösseren Bereichen sind sicherlich verschiedene Optionen der Wiederverwendbarkeit sinnvoll.
• Nur mal so: Ich finde es schwierig, solche bereits optimierten Quelltexte zu lesen. Sie sind zwar formatiert, enthalten aber noch viel Zeug drumherum, Einlesen von Daten, Ausgabe von Daten, etc. Kann sein, dass nur ich das so sehe... dann verzeiht mir bitte, aber ansonsten wäre Pseudocode bzw. nur der wirklich wichtige Code-Ausschnitt imo wesentlich einfacher zu analysieren.
• Denkanstösse gibt es unter anderem auf der gerngelesenen Wikipedia, wo auch ich mein geliebtes Sieb dieses schwer zu schreibenden Mathematikers wiedergefunden habe.
• Das wäre auch mal ein schönes Topic für einen Contest gewesen, (den Meister Ineluki mit seinen Assemblerkenntnissen wohl gewonnen hätte).

Küsschen,
Feenstaub.