Primzahlenprogramm (Verschnellerung)

moin


Du erstellst ein Array von ints, und kopierst dann die Werte nacheinander rein.
Kann dir jetzt kein Beispiel mehr machen, muss schlafen.
Wenn dir morgen noch keiner ne Lösung gegeben hab, werd ich es tun.


mfg
umbrasaxum
 
Hy!

Du kannst die Ergebnisse z.B. in ein Array speichern.
Da du oben gesagt hast, das ihr noch nicht durchgenommen habt was ein Array ist, hier mal eine kurze Beschreibung:
Ein Array könntest du dir als List von Werten vorstellen. Wenn du z.B.
Code:
int myArray[30];
schreibst, hast du 30 Variablen des Typs Integer zur Verfügung.
Diese kannst du dann mit
Code:
myArray[4] = 123;
cout << myArray[4];
...
ansprechen. Wichtig ist nur, das man wenn man 30 Elemente reserviert die Indizes 0...29 zur verfügung hat, wenn man darüber hinaus versucht etwas zu machen, stürtzt dein Programm warsch. ab.

Etwas genauer ist es z.B. hier beschrieben

mfg
uhu01
 
Hy!

Sicherlich:

Code:
#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <windows.h>
#include <time.h>

#define MAX_PRIME_COUNT 1000

int main() {
  int w, x, y, z, a, iSqrt, iAktPrime = 0;
  int piPrimes[MAX_PRIME_COUNT];
  long zeit1,zeit2,zeit;
  memset( piPrimes, 0, MAX_PRIME_COUNT);

  time( &zeit1);
  for( w = 3; w < 10000000 && iAktPrime < MAX_PRIME_COUNT - 1; w += 2) {
    y = 0;
    iSqrt = sqrt(w)
    for( x=2; x < iSqrt; x++) {
      z = w % x;

      if(z == 0) {
        y++;
        break;
      }
    }
    if(y == 0) {
      piPrimes[ iAktPrime++] = x;
    }   
  }
  time(&zeit2);
  zeit= zeit2 - zeit1;
  for( x = 0; x < MAX_PRIME_COUNT && piPrimes[x] != 0; x++) {
    cout << piPrimes[x] << endl;
  }
  getch();
}

Ich hoffe mal das ich keinen Fehler gemacht hab, hab's nicht getestet.
Sollten mehr als 1000 Primzahlen herauskommen, musst du den MAX_PRIME_COUNT erhöhen, nach der 1000sten Primzahl wird nämlich abgebrochen. ( && iAktPrime < MAX_PRIME_COUNT - 1)

mfg
uhu01
 
Zuletzt bearbeitet:
Hy!

Ich hab den Fehler gefunden:
Ich habe statt w immer x ins Array geschrieben, das was du gesehen hast war also nur die falsche Variable

Für größere Werte von MAX_PRIME_COUNT beendet das Programm jedoch mit einem Stack Overflow.
Dies kannst du dadurch beheben, indem du piPrimes auf den Heap legst:
Code:
int *piPrimes = new int[MAX_PRIME_COUNT];
statt
int piPrimes[MAX_PRIME_COUNT];

Allerdings wird das Programm dann beim starten um einiges langsamer.
Du könntest allerdings auch das Array wieder von vorne zu beschreiben beginnen, dann hättest du z.B. nur die 1000 größten Primzahlen

EDIT:
Ich hab die zweite Schleife noch auf
Code:
for( x=3; x < iSqrt; x+=2)
geändert, und bin damit auf 23 runtergekommen

EDIT:
Nochmal schneller müsste es werden wenn du die zweite Schleife durch
Code:
for( x = 0; x <= iAktPrime && piPrimes[x] < iSqrt; x++)
  z = w % piPrimes[x];
Das wird das Programm vor allem bei größeren w um einiges schneller machen

mfg
uhu01
 
Zuletzt bearbeitet:
moin


Was du auch noch machen könntest ist die Priorität deines Programms gegenüber anderen Programm zu erhöhen, um sicher zustellen das dein Programm so schnell wie möglich laufen kann.


mfg
umbrasaxum
 
Man kann das Wurzelziehen auch ganz weglassen, wenn man
Code:
y=0;
		
                wurzel = sqrt(w)+1;
		for(x=2;x<wurzel;x++)
		{

durch
Code:
y=0;
		
                for(x=2;(x*x)<(w+1);x++)
		{

ersetzt... ;)
Vielleicht kann man sogar anstatt w+1 nur w nehmen...
 
umbrasaxum hat gesagt.:
moin


Was du auch noch machen könntest ist die Priorität deines Programms gegenüber anderen Programm zu erhöhen, um sicher zustellen das dein Programm so schnell wie möglich laufen kann.


mfg
umbrasaxum
naja ... das ist dann aber nicht wirklich eine Programmoptimierung. Mit dem Eurestatos Algo, den ich weiter oben vorgestellt hatte, habe ich im uebrigen die Laufzeit um mehr als ein drittel reduziert.
 
Zurück