Dann wäre das ganze auch langweiligLeonidas hat geschrieben:Leider gibt es die Quellcodes nirgendwo öffentlich, was aber auch irgendwie verständlich ist.

Wie ich schon in vorherigen Beiträgen geschrieben habe, kann die Lösung nicht so funktionieren, dass man das gesamte Intervall von 1 bis 1 Mrd. in das Sieb steckt. Selbst wenn es keinen Speicherfehler gäbe, wäre das nicht der richtige Weg.Graf Wasserrutsche hat geschrieben:Kannst du mir evtl. doch noch weitere Ratschläge geben, wie ich bei dem Primzahlproblem weiterkommen könnte? Ich steck da sowas von fest, dass ich nicht mehr nach vorne und nach hinten weiss.
Oder gib mir nur einen kleinen Tipp. Wenn ich die Liste ja bis 1.000.000.000 befüllen will gibt es einen MemoryError. Wie umgehe ich diesen bzw. wie ermittle ich, bis zu welchem Wert ich überhaupt rechnen muss damit alles nötige abgedeckt ist?
0.12 s auf meinem (fast 8 Jahre alten) Rechner.HerrHagen hat geschrieben:Eins wird mich dann noch interessieren: Wie lang braucht dein Algorithmus eigentlich für den Bereich (1000000000, 1000000000-100000)? Ich weiß nicht so recht wie stark ich meine Lösung einzuschätzen ist und ob des sich lohnt meinen Lösungsansatz weiterzuentwickeln...
Sollen wir es mal mit einem etwas schnelleren CPU testen? :>numerix hat geschrieben:0.12 s auf meinem (fast 8 Jahre alten) Rechner.
3.0 tut es genausowenig. Wobei, eigentlich ist die Sache etwas komplizierter als das. Siehe Diskussionen zu GIL.Craven hat geschrieben:Da fällt mir gerade ein, Python 2.5 bzw. 2.6 unterstützt ja noch garkeine Dual Cores, oder?
Wenn du die Idee des Siebes wirklich - so durch und durch! - verstanden hast, dann hast du alles, was du brauchst. Schreib dir doch mal das Sieb von z.B. 35 bis 70 auf und führe die dann zu tuenden Schritte manuell durch. Mach dir Gedanken über die Zahlen, die gestrichen werden und wie du an die Zahlen herankommst. Der Rest ist im Prinzip nichts anderes, als eine gründliche Analyse dessen, was du siehst. Und dann die gewonnenen Erkenntnisse in einen Algorithmus umsetzen.Graf Wasserrutsche hat geschrieben:Jetzt wird auf jeder Seite die ich gefunden habe gezeigt wie man das Problem mit einem Sieb, beginnend mit der Zahl 2 löst, aber nicht, mit einem Sieb welches z.B. mit 35 beginnt. Muss ich nicht trotzdem diverse Zahlen vor dem Bereich ausrechnen, um bestimmte Zahlen in diesem Sieb streichen zu können, oder gibt es da noch eine andere Möglichkeit?
Vielleicht habt ihr ja auch Quellen, mit welchen ich mir das benötigte auch anlesen kann.
Code: Alles auswählen
from math import sqrt
import psyco
psyco.full()
def sieve(m,n):
sieve = range(m,n+1)
max_divider = int(sqrt(n))/2
curr_divider = 2
while curr_divider <= max_divider:
for i in range(0,len(sieve)):
if int(sieve[i]) == curr_divider:
pass
elif int(sieve[i]) % curr_divider == 0:
sieve[i] = 0
curr_divider += 1
return sieve
for i in sieve(35,70):
if i != 0:
print i
Craven hat geschrieben:Wird Psyco denn überhaupt akzeptiert von SPOJ?
Wobei man den Aufwand aber gegeneinander abwägen muss. Möglicherweise wird es teurer, die Werte herauszurechnen, die man nicht erneut streichen muss, als diese einfach nochmal zu streichen.HerrHagen hat geschrieben:Wie wärs z.B. damit:
Wenn du bspw. schon alle Vielfachen von 3 gestrichen hast brauchst du bei der nächsten Primzahl 5 dann 5*3, 5*6, 5*9 ... nicht mehr streichen.
Code: Alles auswählen
def sieve(m,n):
sieve = range(m,n+1)
max_divider = int(sqrt(n))/2
curr_divider = 2
while curr_divider <= max_divider:
for i in range(0,len(sieve)):
if sieve[i] != 0:
if int(sieve[i]) == curr_divider:
pass
elif int(sieve[i]) % curr_divider == 0:
sieve[i] = 0
curr_divider += 1
return sieve
Möchte das nochmal unterstreichen und einmal mehr meiner Begeisterung über Python Ausdruck verleihen: Durch eine kleine Änderung an meinem Code, die lediglich einen der Kernabläuf "pythonischer" macht, ist es gelungen, die bisherige Lösung noch einmal schneller zu machen: Die letzte Fassung war mit 0.40 s SPOJ-Laufzeit ja auch schon nicht gerade langsam, hat das aber nur mit psyco geschafft. Jetzt sind es 0.35 s und zwar OHNE PSYCO. Python ist toll!numerix hat geschrieben:Wobei man den Aufwand aber gegeneinander abwägen muss. Möglicherweise wird es teurer, die Werte herauszurechnen, die man nicht erneut streichen muss, als diese einfach nochmal zu streichen.HerrHagen hat geschrieben:Wie wärs z.B. damit:
Wenn du bspw. schon alle Vielfachen von 3 gestrichen hast brauchst du bei der nächsten Primzahl 5 dann 5*3, 5*6, 5*9 ... nicht mehr streichen.
Code: Alles auswählen
primes = (3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,
181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,
277,281,283,293,307,311,313)
def primefilter(start, stop):
if start%2: start += 1
primfilter = ' and '.join(["n%%%s" % p for p in primes])
return eval("[n for n in range(%s, %s, 2) if %s]" % (start, stop, primfilter))
start = int(raw_input("start"))
stop = int(raw_input("stop"))
from time import clock
t = clock()
primefilter(start, stop)
print clock() - t