SAGE: Sieb von Erathosthenes

Neue Frage »

JuPee Auf diesen Beitrag antworten »
SAGE: Sieb von Erathosthenes
Meine Aufgabe:
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 ...
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.
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" ...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von JuPee
Und wie würdest du das dann oben einbauen?

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. Augenzwinkern


Ansonsten verweise ich nochmals auf meine fehlenden SAGE-Kenntnisse.
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...
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 Big Laugh Wo ist jetzt noch der kleine Fehler?
 
 
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von JuPee
Jetzt bleibt aber komischerweise immer nur die 2 als Primzahl übrig Big Laugh Wo ist jetzt noch der kleine Fehler?

Nachfolgend in rot deine, äh, "kleinen" Fehler... unglücklich

Zitat:
Original von JuPee
def sieb(n):
___primzahlen = [2..n]
___for p in [2..n]:
_____if primzahlen[p-2]>0:
_______for i in [p^2-2 .. n-2]: primzahlen[i] = 0
___while 0 in primzahlen: primzahlen.remove(0)
___print primzahlen


Edit: Nach wie vor bin ich aber der Meinung, dass diese Lösung alles andere als "elegant" ist...
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. verwirrt
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 Big Laugh

@ 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?
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
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.

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)...

Zitat:
Original von HAL 9000
Ich würde entweder ebenfalls das von vornherein unsinnige

primes[2...n]

ersetzen durch

primes[0..n]
primes[0]=0
primes[1]=0
[...]


Edit: Außerdem sehe ich gerade, dass es da natürlich primes=[2..n] bzw. primes=[0..n] heißen muss...
BCS2910 Auf diesen Beitrag antworten »

So ganz uneigennützig wie wäre es den hier mit bis jetzt hatte ich keine probleme damit Augenzwinkern


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
JuPee Auf diesen Beitrag antworten »

@BCS2910:

siehe private Nachricht.
Airblader Auf diesen Beitrag antworten »

Mal ein allgemeiner Tipp: Die [ code ]-Tags sind bei diesen Threads echt nützlich:

code:
1:
2:
3:
4:
5:
6:
7:
8:
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


air
Mystic Auf diesen Beitrag antworten »

@air

Musstest du wirklich Salz in seine Wunden streuen, indem du ausgerechnet seinen extrem fehlerhaften Code hier nochmals reinstellst? Big Laugh
Airblader Auf diesen Beitrag antworten »

Ja. Big Laugh

(Ich hatte nicht drauf geachtet Augenzwinkern )

air
JuPee Auf diesen Beitrag antworten »

@ Mystic:

Nur weil dein Code eine Primzahl mehr anzeigt, ist er ja jetzt nicht unbedingt besser Augenzwinkern

Und meine Frage mit der Aufgabenstellung hast du auch noch nicht beantwortet ...
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von JuPee
@ Mystic:

Nur weil dein Code eine Primzahl mehr anzeigt, ist er ja jetzt nicht unbedingt besser Augenzwinkern

Sorry, ich weiss natürlich nicht, was jetzt das exakte Äquivalent in SAGE ist, aber das entsprechende Programm in Maple funktioniert:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
sieb :=proc(n)
   local i,primes:=Array(0..n-2,[$2..n]),p;
   for p in [$2..n] do
     if primes[p-2]>0 then
       for i from p^2-2 to n-2 by p do primes[i]:=0 end do
     end if
   end do;   
   seq(primes[i],i=0..n-2) 
end:        

sieb(20);

   2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0

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"...

Zitat:
Original von JuPee
Und meine Frage mit der Aufgabenstellung hast du auch noch nicht beantwortet ...

Ich sehe überhaupt nicht, warum eine Indexverschiebung - wie immer man sie jetzt realisiert - der Aufgabenstellung nicht gerecht werden sollte... verwirrt

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...
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »