Primzahlenprogramm

[cartman]

hi leutz!

brauche ein programm das alle primzahlen errechnet die sich innerhalb der eingegebenen zahl befinden. außerdem sollte noch die laufzeit bis zur ausgabe der ermittelten primzahlen ausgegeben werden.

wenn jemand so ein programm hat oder weiß wo ich ein solches

finden kann bitte informationen posten an:

fat_cartman@web.de

danke

cartman

[doublezero]

Um alle Primzahlen "innerhalb einer eingegebenen Zahl" zu ermitteln, gibt es verschiedene Verfahren.

Das einfachste - und durchschaubarste - ist das

Siebverfahren des Erastosthenes

-----------------------------------

Nimm eine (unendliche) Liste aller natürlichen Zahlen > 1.

Die erste Zahl der Liste (2) ist eine Primzahl. Nun entfernst du alle Vielfachen von 2 aus dieser Liste. Dann nimmst du die nächstgrößte Zahl (3). Auch diese Zahl müsste dann wohl eine Primzahl sein. Jetzt werden alle Vielfachen von 3 aus dieser Liste entfernt. Die nächste Zahl ist 5. Auch sie ist eine Primzahl ... usw. usf.

Dieses Verfahren dauert schöööön lange; ist aber ausgesprochen präzise und "vergisst" keine Primzahl der Liste.

Alternativ kannst du auch die

normale Division:

-----------------

verwenden. Dabei kannst du jede Zahl deiner Liste m durch alle Zahlen n,

wobei 2 <= n <= Wurzel(Testzahl)

teilen. Wenn der Rest immer größer 0 ist, dann sollte die Zahl wohl prim sein.

Das letztere Verfahren lässt sich mit der

wheel factorization:

--------------------

noch erheblich verfeinern und damit beschleunigen:

Nimm eine Liste natürlicher Zahlen m möglicher Teiler der Zahl n,

wobei 2 <= m <= Wurzel(Testzahl).

Ermittle hier die primen Zahlen, indem du alle Zahlen deiner Liste streichst, die sich durch 2, 3 und 5 teilen lassen. Setze dieses Verfahren für alle verbleibenden Zahlen fort ...

Der Vorteil hier ist, dass die zweite Liste parallel zur ersten (der "Test-Liste") wächst und nur einmal errechnet werden muss. Das beschleunigt den Vorgang erheblich, denn spannend werden solche Testverfahren erst bei den richtig großen Zahlen.

Wenn du Timer in die Loops hängst, dann kannst du die Dauer deines "Ermittlungsverfahrens" bis zum tick genau bestimmen.

wmg,

dz

PS: Falls du diese Berechnungen für Verschlüsselungsverfahren brauchst: Es gibt andere - leichtere und damit schnellere - Wege des Testens, ob eine bestimmte Zahl prim ist oder nicht. Allerdings bauen diese Verfahren keine integralen Listen auf, sondern testen lediglich selektiv.

--------------------

Es gibt zwei unverrückbare Grundsätze auf der Welt:

1. Der Computer nutzt dem Menschen.

2. Die Erde ist eine Scheibe.

<FONT COLOR="#a62a2a" SIZE="1">[ 30. Oktober 2001 13:48: Beitrag 3 mal editiert, zuletzt von doublezero ]</font>

[cartman]

danke doublezero!

wo ich ein solches programm, egal welchen verfahrens finde,

weißt du nicht zufällig? brauche das für php 4!

thx

cartman :confused:

[doublezero]

Sorry,

aber ein Programm, das Primzahlberechnungen quasi zum Selbstzweck hat, ist mir nicht geläufig, weil es i.d.R. lediglich EIN Teilproblem darstellt, Primzahlen zu ermitteln.

Wie wäre es denn, wenn du diese Aufgabe - natürlich nur so als Fingerübung - selbst schreibst ?! Es ist gewiss nicht allzu schwierig.

wmg,

dz

[ypper]

falls du nicht so gut bist im problemlösungen bearbeiten, hab ich hier ein kleines beispiel in c++ code mit dem man deine aufgabe lösen könnte ;-)

void main (void)

{

int eingabe;

bool prim;

cout<<"Eingabe bis zu welcher zahl nach Primzahlen gesucht werden soll: ";

cin>>eingabe;

for(int i=2; i<=eingabe;i++)

{

prim=true;

for (int k=2; k<= i;k++)

{

if i%k ==0

{

prim =false;

}

if prim == true

cout<<"eine primzahl wäre:";

}

}

getch();

}

je höher deine eingabezahl ist desto langsamer wird das programm in seinem verlauf.

p.s.: falls dir knapp 65000 werte nicht ausreichen deklariere eingabe einfach als long int oder höher.

wegen dem laufzeit anzeigen muss ich nochmal kucken:-)

p.p.s.: wenn du von mir ein fertiges programm in php4 haben willst (source code) dann schreib mir doch ne mail und wir können uns über die zahlungsmodalitäten unterhalten :-))

<FONT COLOR="#a62a2a" SIZE="1">[ 02. November 2001 22:17: Beitrag 4 mal editiert, zuletzt von ypper ]</font>