Algorithmus: Primzahlen bestimmen |
| 04.04.2006, 10:25 | wolfgang_1 | Auf diesen Beitrag antworten » | ||
| Algorithmus: Primzahlen bestimmen Ich würde gerne einen ökonomischen Algorithmus schreiben, der für eine gegebene Zahl n alle Primzahlen bestimmt, welche <= n sind. Ich hab dazu auch schon eine Idee: Ich wollte rekursiv vorgehen bis ich alle Primzahlen <= n-1 habe und dann überprüfen ob n selbst eine Primzahl ist. Hat irgendjemand eine Idee, wie ich das in einen Algortihmus kriege? Versuche das jetzt schon seit Stunden ohne Erfolg. ;-( Danke, Wolfgang |
||||
| 04.04.2006, 10:32 | Dual Space | Auf diesen Beitrag antworten » | ||
| RE: Algorithmus: Primzahlen bestimmen Wenn das Script häufig genutzt werden soll, würde ich behaupten es wär am effizientesten alle Primzahlen bis zu einer für deine Anwendung hinreichend große Zahl N einmalig zu berechnen und zu speichern. Dann kannst du mit einem simplen vergleich der Primzahlen mit der Eingabe n die gesuchten Primzahlen ausgeben lassen. Die Primzahlen, kannst du z.B. mit dem "Sieb des Eratosthenes" erzeugen. Das "Sieb des Eratosthenes" funktioniert im klassischen Sinne folgendermaßen: 1. Schreibe alle natürlichen Zahlen von 2 bis zu einer beliebigen Zahl n auf. 2. Streiche alle Vielfachen von 2 heraus. 3. Gehe zur nächstgrößeren nichtgestrichenen Zahl und streiche deren Vielfache heraus. 4. Wiederhole 3. sooft es geht. 5. Die übriggebliebenen Zahlen sind Primzahlen. Edit: Falls du das Speichern nicht so elegant findest, liefert dir das "Sieb..." natürlich auch alleine das gewünschte Ergebnis. Allerdings bin ich mir nicht sicher, ob dieser Algorithmus wirklich effizient ist. |
||||
| 04.04.2006, 10:39 | wolfgang_1 | Auf diesen Beitrag antworten » | ||
| RE: Algorithmus: Primzahlen bestimmen Danke. :-) Du hast mir sehr geholfen. lg, Wolfgang |
||||
| 04.04.2006, 10:52 | Dual Space | Auf diesen Beitrag antworten » | ||
You are 
!Btw: C. F. Gauß soll angeblich nach diesem Verfahren die ersten 3 Millionen Primzahlen handschriftlich(!!) durchgesiebt haben. 
|
||||
| 04.04.2006, 11:02 | AD | Auf diesen Beitrag antworten » | ||
Bist du dir da sicher? Vielleicht waren's auch nur 3000, und die folgenden drei Nullen entstanden durch Legendenbildung. 
|
||||
| 04.04.2006, 23:12 | Ben Sisko | Auf diesen Beitrag antworten » | ||
RE: Algorithmus: Primzahlen bestimmen
Was ist ein "ökonomischer" Algorithmus? Ökonomisch im Sinne von effizient? |
||||
| Anzeige | ||||
|
|
||||
| 05.04.2006, 03:08 | sqrt(2) | Auf diesen Beitrag antworten » | ||
Wenn die Primzahlbestimmung mit einem Rechner erfolgen soll, ist dieser Link vielleicht ganz interessant. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
