SAGE: Sieb von Erathosthenes |
25.04.2012, 12:40 | JuPee | Auf diesen Beitrag antworten » | |||||||||
SAGE: Sieb von Erathosthenes Man implementiere in SAGE eine Funktion sieb, die einen Parameter übergeben bekommt und mit dem Sieb des Eratosthenes die Liste der Primzahlen zwischen 2 und n einschließlich berechnet. Meine Idee: def sieb(n): ___primes = [2..n] ___for p in [2..sqrt(n)]: _____if primes[p]>0: _______for i in [p^2 .. n, step = p]: primes[i] = 0 ___while 0 in primes: primes.remove(0) ___return primes Die Unterstrichte sollen ledigliche die Einrücke verdeutlichen. Warum zeigt SAGE mir Error an? Wenn man das Intervall primes = [0..n] nimmt und primes[1]=0 ausschließt, dann klappt es komischerweise. Aber das ist ja laut Aufgabenstellung nicht möglich ... |
|||||||||||
25.04.2012, 14:09 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Ich hab keine Ahnung von diesem SAGE, aber die Verwandtschaft zu C lässt mich erahnen, dass eine Deklaration wie primes = [2..n] folgende Vorbelegung von primes (als Feld betrachtet) zur Folge hat: primes[0] = 2 primes[1] = 3 primes[2] = 4 ... primes[n-2] = n Der Error wäre dann verständlich... Aber ich kann mich auch irren, denn wie gesagt: Ich kenne dieses SAGE nicht. |
|||||||||||
25.04.2012, 15:58 | JuPee | Auf diesen Beitrag antworten » | |||||||||
Und wie würdest du das dann oben einbauen? Ich bin total am verzweifeln -.- Und es gibt noch eine "SAGE-Aufgabe" ... |
|||||||||||
25.04.2012, 16:28 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Ich habe lediglich eine passende Theorie geäußert, warum es mit primes = [0..n] klappt, mit primes = [2..n] aber nicht - mehr nicht. Du könntest diese Theorie ja prüfen, indem du es mal mit primes = [2..n+2] versuchst. Dann kommt wohl kein Error, wohl aber die "falschen" Primzahlen. Ansonsten verweise ich nochmals auf meine fehlenden SAGE-Kenntnisse. |
|||||||||||
25.04.2012, 17:02 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Ich würde entweder ebenfalls das von vornherein unsinnige primes[2...n] ersetzen durch primes[0..n] primes[0]=0 primes[1]=0 oder die Laufindices in den for-Schleifen entsprechend anpassen,d.h., generell um 2 vermindern, was mir aber jetzt nicht wirklich gefällt... |
|||||||||||
29.04.2012, 16:47 | JuPee | Auf diesen Beitrag antworten » | |||||||||
@Mystic: So wie du es jetzt aufgeschrieben hast, hatte ich es am Anfang und damit klappt es auch. Aber widerspricht das nicht der Aufgabenstellung, dass man der Funktion ein geben soll? Ich habe das mit der Grenzenverschiebung jetzt mal gemacht: def sieb(n): ___primzahlen = [2..n] ___for p in [0..(n-2)]: _____if primzahlen[p]>0: _______for i in [p^0 .. n-2]: primzahlen[i] = 0 ___while 0 in primzahlen: primzahlen.remove(0) ___print primzahlen Jetzt bleibt aber komischerweise immer nur die 2 als Primzahl übrig Wo ist jetzt noch der kleine Fehler? |
|||||||||||
Anzeige | |||||||||||
|
|||||||||||
29.04.2012, 19:43 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Nachfolgend in rot deine, äh, "kleinen" Fehler...
Edit: Nach wie vor bin ich aber der Meinung, dass diese Lösung alles andere als "elegant" ist... |
|||||||||||
30.04.2012, 08:15 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
@JuPee Ich deute mal Mystics Beiträge so, dass ich mit meiner obigen Vermutung zur SAGE-Syntax insoweit richtig lag, dass in deinem primes-Array Index und Feldinhalt am Anfang (und bei den unveränderten Array-Elementen auch bis zum Schluss) um genau 2 verschoben sind. Da muss ich mich schon sehr wundern, dass du da nicht endlich mal gründlich drüber nachdenkst und stattdessen mit deiner frisch-fröhlichen Trial-und-Error-Programmierung fortfährst. |
|||||||||||
30.04.2012, 10:28 | JuPee | Auf diesen Beitrag antworten » | |||||||||
@ HAL 9000 Doch, doch. Da habe ich mir schon Gedanken drüber gemacht. Ich habe ja bei meinem letzten Beitrag den Index von p und i jeweils um 2 verschoben. Aber SAGE scheint nicht so einfach zu sein, weil mit der Lösung von Mystic klappts immer noch nicht ... Bei sieb(10) bleiben jetzt nur die 2 und 3 stehen ... Ich hoffe ihr könnt so langsam nachvollziehen, warum mich das Programm wahnsinnig macht @ Mystic: Wenn ich die Lösung (mit Intervall von 0 bis n und die 0 und 1 ausschließe) nehmen würde, die ja funktioniert, widerspricht das dann nicht der Aufgabenstellung? |
|||||||||||
30.04.2012, 10:34 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Ja, das war auch von Anfang an klar, auch wenn ich mich zugegebenermaßen nur sehr vage auf dein Posting bezogen habe (s.u., mit nachträglicher Hervorhebung)...
Edit: Außerdem sehe ich gerade, dass es da natürlich primes=[2..n] bzw. primes=[0..n] heißen muss... |
|||||||||||
30.04.2012, 17:12 | BCS2910 | Auf diesen Beitrag antworten » | |||||||||
So ganz uneigennützig wie wäre es den hier mit bis jetzt hatte ich keine probleme damit def sieb(n): P = range(2,n+1) i = 0 p = P[i] while p*p <= n: v = 2*p while v <= P[-1]: if v in P: P.remove(v) v = v+p i = i+1 p = P[i] return P ps.: falls du bei skoruppa zth hörst wäre ich über nen tipp bei der nr 3 sehr glücklich |
|||||||||||
30.04.2012, 17:28 | JuPee | Auf diesen Beitrag antworten » | |||||||||
@BCS2910: siehe private Nachricht. |
|||||||||||
30.04.2012, 18:00 | Airblader | Auf diesen Beitrag antworten » | |||||||||
Mal ein allgemeiner Tipp: Die [ code ]-Tags sind bei diesen Threads echt nützlich:
air |
|||||||||||
30.04.2012, 18:11 | Mystic | Auf diesen Beitrag antworten » | |||||||||
@air Musstest du wirklich Salz in seine Wunden streuen, indem du ausgerechnet seinen extrem fehlerhaften Code hier nochmals reinstellst? |
|||||||||||
30.04.2012, 18:24 | Airblader | Auf diesen Beitrag antworten » | |||||||||
Ja. (Ich hatte nicht drauf geachtet ) air |
|||||||||||
01.05.2012, 11:25 | JuPee | Auf diesen Beitrag antworten » | |||||||||
@ Mystic: Nur weil dein Code eine Primzahl mehr anzeigt, ist er ja jetzt nicht unbedingt besser Und meine Frage mit der Aufgabenstellung hast du auch noch nicht beantwortet ... |
|||||||||||
01.05.2012, 13:02 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Sorry, ich weiss natürlich nicht, was jetzt das exakte Äquivalent in SAGE ist, aber das entsprechende Programm in Maple funktioniert:
Ich habe dabei absichtlich die Nullen in der Ausgabe noch nicht entfernt, damit man besser sieht, dass sie vor der Entfernung an den "richtigen Stellen sitzen"...
Ich sehe überhaupt nicht, warum eine Indexverschiebung - wie immer man sie jetzt realisiert - der Aufgabenstellung nicht gerecht werden sollte... Edit: Da wird schon eher der Aufgabenstellung, also einer möglichst originalgetreuen Implementierung des Siebs des Eratosthenes, nicht gerecht, dass p alle Zahlen von 2 bis n durchläuft, statt nur bis zur Wurzel aus n... |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|