✔ Primzahlenprogramm (Verschnellerung)

A

Andreas703

Mitglied
Also
Ich habe DevCpp von Bloodshed und arbeite unter Windows

Ich soll dieses Programm soweit wie möglich verschnellern(Es ist ein von mir selbstgeschriebenes Programm, aber es geht angeblich schneller und der Lehrer gab dies gleich mal als Aufgabe für mich, ob ich herausfinde wies geht, also machts auch nix wenn ichs nicht herausfinde ^^)
Ich hoffe trotzdem das ihr mir helfen könnt da es bis zum aufzählen aller Primzahlen bis 10 mio immerhin über 100 sec dauert( ich denke sogar 136 sec waren es)
Achja... die Ausgabe und der Timebefehl sollten bitte bleiben^^

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


int main()

{
	int w,x,y,z,a;
	long zeit1,zeit2,zeit;

	time(&zeit1);
	for(w=3;w<10000000;w++)
	{
		y=0;
		
		for(x=2;x<(sqrt(w)+1);x++)
		{
			z=w%x;
			
			if(z==0)
			{
				y++;
				break;
			}
		}
		
			if(y==0)
			{
				cout<<<"\n";
			}	   
	}	
	time(&zeit2);
	zeit= zeit2 - zeit1;
	cout<
	getch();
}
 
moin


Du könntest w immer um 2 erhöhen, da gerade Zahlen eh keine Primzahlen seien können.
So würdest du dir die Hälfte der Berechnungen sparen können.

Edit:
Ich muss mich korrigieren, du sparst nciht die Hälfte der Berechnugnen, sonder nur etwa 5000000.


mfg
umbrasaxum
 
Zuletzt bearbeitet:
moin


Hab mal ein bischen getestet.
So wie du den Code oben gepostet hast, brauche ich: 53
Mit w+=2 statt w++, brauche ich: 51

Außerdem hab ich mal gelesen das die Berechnung der Wurzel, mit inline-Assembler auch noch schnell gehen soll.


mfg
umbrasaxum
 
erstens: du kannst für w die Liste der schon berechneten Primzahlen nehmen anstatt immer um 2 zu erhöhen. Ab 1000 sollte das einen Geschwindigkeitsplus von mind. 100% bringen...

zweitens: du könntest die Wurzelfunktion mittels des Heron-Verfahrens :google: in inline-Assembler schreiben um einen weiteren Geschwindigkeits+ zu bekommen

hope it was halp for you
 
Ich denke auch ein besserer Algorithmus ist erstmal besser, als Assembler. Schaetz auch mal dein Lehrer wolte das. Hab mal schnell das Verfahren von Eratosthenes gecodet (soweit ich weiss fuer kleine Primzahlen (klein = unter 10Millionen). Das Prinzip ist, du erstellst eine Liste aller Zahlen bis zu deiner maximalen Zahl. Dann beginst du mit 2 und streichst alle Zahlen, die durch zwei teilbar sind. Dann gehst du zur naechsten nicht gestrichenen Zahl und streichst alle durche diese teilbaren Zahlen. wenn du fertig bist, sind die uebriggebliebenen Zahlen Primzahlen:
Code: 
#include <iostream>
#include <cmath>
#include <ctime>

using namespace std;

int main(void) {
    time_t t1=time(0);

    long max=1000000;
/* Erstellle Zahlenliste */
    bool m[max];
    for (int i=0;i<max;m[i++]=true)
	;

/* Gehe durch alle ungestrichenen Zahlen und streiche Vielfache */
    for (int i=1;i<(sqrt((float) max));i++) {
	if (m[i])
	    for (int n=2;n*(i+1)<=max;n++)
		m[n*(i+1)-1]=false;
    }

/* Gebe alle ungestrichenen Zahlen aus */
    for (int i=1;i<max;i++)
	if (m[i])
	    cout << i+1 << "\n";

    time_t t2=time(0);
    double d =difftime(t2,t1);

    cout << scientific << d << endl;

    return 0;
}
Das Verfahren ist jetzt noch suboptimal. Insbesondere liesse sich da bei dem Array einiges machen (Stichwort Bit-operationen). Aber ich wollte es erstmal moeglichst verstaendlich schreiben. Und ich vergeude im Array Platz (zB ungenutze 1 Eintrag ...). Und den zweier Durchgang kannst du dir eigentlich auch komplet sparen ...

Eine erste Optimierung wuerde dann so aussehen:
Code: 
#include <iostream>
#include <cmath>
#include <ctime>

using namespace std;

int main(void) {
    time_t t1=time(0);

    unsigned long max=1000000; 
    bool m[(max-1)/2]; /* Nimmt man von vornerein alle geraden
                                      Zahlen heraus und die 1, braucht man
                                      weniger Platz und weniger Tests */

    for (int i=0;i<(max-1)/2;m[i++]=true)
	;

   /* ein bischen einfachste Mathematik 
       aendert dann die Schleife. Der erste Testwert und auch
       der erste Muliplikator ist jetzt 3. Wir multiplizieren jetzt auch
       nur noch mit ungeraden Werten. */
    for (int i=0;2*i+3<(sqrt((float) max));i++) {
	if (m[i])
	    for (int n=0;(2*n+3)*(2*i+3)<=max;n++)
		m[2*n*i+3*(n+i)+3]=false;
    }

    /* Ausgabe muss auch an das neue Array angepasst werden */
    for (int i=0;i<(max-1)/2;i++)
	if (m[i])
	    cout << 2*i+3 << "\n";

    time_t t2=time(0);
    double d =difftime(t2,t1);

    cout << scientific << d << endl;

    return 0;
}
 
Zuletzt bearbeitet:
sry aber alles außer dem w+=2 ist mir leider alles zu hoch :( könntet ihr auf mein Niveau runterkommen ?^^

Zum Bsp den Inline Assembler check ich nicht und was Arrays sind weiß ich auch noch nicht :(
 
moin


Auf http://www.primzahlen.de gibt es einige nützliche Informationen, über verschiedene Verfahren, Algorythmen Beispiele, und jede Menge anderer Informationen.

Guck es dir einfach mal an bzw. liess es.

Edit:
:rolleyes: Du weisst noch nciht was Arrays sind?! Dann mach dich erstmal an die Grundlagen, bevor du versuchst einen Code zu schreiben der annähernd den Codes entspricht, die heutzutage zur Primzahl findung benutzt werde.

Trotzdem finde ich das diese ganze Sache auch für Erfahrene eine gute Übung ist.


mfg
umbrasaxum
 
Zuletzt bearbeitet:
naja was das Prob is is das ich erst seit ca 4 Monaten Proggen lerne und der Lehrer will die Arrays erst nächstes Jahr mit uns durchnehmen ;)
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück