SPOJ - PRIME1 - Primzahlengenerator

Code-Stücke können hier veröffentlicht werden.
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Mittwoch 4. Februar 2009, 11:22

Guten Tag zusammen!

Ich habe ein Problem mit der Aufgabe zur Erstellung eines Primzahlengenerators. Ich habe jetzt schon ein paar Hürden überwunden, wie z.B. das "time limit exceeded", welches ich durch Psyco umgangen habe (ja, ich weiss, ein besserer algorithmus hätte das auch getan, vielleicht kann mir da ja auch jemand helfen, weil ich echt nicht weiter weiss), dann wurde ein NZEC-Fehler ausgegeben, welche ich mit einer exception abgefangen habe.

Jetzt habe ich genau die Ausgabe welche gewünscht ist (Habe zur Übersicht Input und Output mit reingenommen), und ansich wird auch alles richtig berechnet. Ich bekomme dennoch eine "wrong answer"-Fehlermeldung ausgegeben.

Weiss vielleicht einer von euch was ich falsch gemacht habe? Ich weiss das der Code wahrscheinlich total aufgeblasen ist, muss mir noch guten Programmierstil aneignen. Über Verbesserungsvorschläge würde ich mich auch sehr freuen.

Problem ist folgendes: https://www.spoj.pl/problems/PRIME1/

Code: Alles auswählen

from math import sqrt

import psyco
psyco.full()

def sieve(m,n):
    sieve = range(n+1)
    sieve[1] = 0
    
    max_divider = int(sqrt(n))
    curr_divider = 2
    
    while curr_divider <= max_divider:
        lst_index = curr_divider**2
        while lst_index <= n:
            sieve[lst_index] = 0
            lst_index += curr_divider
        curr_divider += 1
        while sieve[curr_divider] == 0:
            curr_divider += 1
    
    for i in range(m,len(sieve)):
        if sieve[i] != 0:
            print sieve[i]
            
def ask(x):
    for i in range(0,x):
        fehler = 1
        while fehler == 1:
            t = raw_input()
            y = t.split()
            if (int(y[1])-int(y[0])) <= 100000 and int(y[1]) <= 1000000000 and int(y[0]) <= int(y[1]) and int(y[0]) >= 1:  
                fehler = 0      
                test.append(y)               
        return test

print 'Input:'
fehler = 1
while fehler == 1: 
    y = int(raw_input())
    if y <= 10:
        fehler = 0
        
test = []
for i in range(0,y):
    t = ask(y)

print ''
print 'Output:'
for i in range(0,len(t)):
    m = test[i][0]
    n = test[i][1]
    try:
        m = test[i][0]
        n = test[i][1]    
        sieve(int(m),int(n))
        if i < len(t)-1:
            print ''
    except:
        pass
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
BlackJack

Mittwoch 4. Februar 2009, 20:58

Die ganzen Fehlerprüfungen auf die Bereiche sind unnötig, weil man schon davon ausgehen kann, dass SPOJ die Zusagen in den Aufgaben auch einhält.

Und wenn schon, dann sollte man für Wahrheitswerte `True` und `False` statt 1 und 0 verwenden.

`ask()` greift auf `test` zu, das ist unübersichtlich. So etwas kann nicht passieren, wenn man möglichst allen Code von der Moduleben in Funktionen verbannt. Und `ask()` ist viel zu kompliziert. Was soll die ``while``-Schleife da?

Es wird oft unnötig indirekt über Indexe zugegriffen. In der letzten Schleife werden `m` und `n` zudem unnötigerweise zweimal die gleichen Werte zugewiesen.

`t` und `test` sind zwar an das gleiche Objekt gebunden, es ist aber trotzdem komisch, dass Du die Länge von `t` nimmst, aber auf `test` zugreifst.


Was für eine Ausnahme behandelst Du da eigentlich?

Ist das exakt das Skript, welches Du ausführst? Wenn ja: Die Ausgaben 'Input:' und 'Output:' gehören da nicht hin.

Zum Algorithmischen: `sieve()` wird bis zu 10 mal aufgerufen und berechnet jedes mal wieder Primzahlen. Es wäre ökonomischer das grösste `n` zu ermitteln und *einmal* alle Primzahlen bis zu diesem Wert zu berechnen und dann immer nur die Zahlen im entsprechenden Bereich auszugeben.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Mittwoch 4. Februar 2009, 22:27

BlackJack hat geschrieben:Zum Algorithmischen: `sieve()` wird bis zu 10 mal aufgerufen und berechnet jedes mal wieder Primzahlen. Es wäre ökonomischer das grösste `n` zu ermitteln und *einmal* alle Primzahlen bis zu diesem Wert zu berechnen und dann immer nur die Zahlen im entsprechenden Bereich auszugeben.
Das ist ganz sicher nicht der richtige Weg, denn das würde ja im ungünstisten Fall bedeuten, dass sämtliche Primzahlen bis 1 Mrd. zu berechnen wäre, obwohl gemäß Vorgabe der insgesamt zu überprüfende Zahlenraum nicht mehr als 1 Mio. Zahlen umfassen kann.

Man sollte günstiger Weise zunächst eine Analyse der Intervalle vornehmen und diese ggf. auf Überschneidungen prüfen.

IMHO dürfte es auf keinen Fall gelingen, die in der Aufgabenstellung vorgegebene Zeit von 6 s mit einem Python-Programm einhalten zu können, sofern man nicht irgendeinen ganz ausgefuchsten Primzahlalgorithmus verwendet. Mit dem Sieb des Eratosthenes oder einem vergleichbar simplen Verfahren wird das in 6 Sekunden nichts.
BlackJack

Mittwoch 4. Februar 2009, 23:54

@numerix: Dumme Frage, aber wie berechne ich die Primzahlen von sagen wir mal 3000000 bis 4000000 ohne die vor 3000000 zu kennen. Mal von probalistischen Tests abgesehen?

Edit: Es gibt auf jeden Fall Python-Lösungen: https://www.spoj.pl/ranks/PRIME1/lang=PYTH
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Donnerstag 5. Februar 2009, 14:09

Alles klar, ich werde die Verbesserungsvorschläge umsetzen, vielen Dank dafür! Ich frage mich nur (abgesehen von dem ausgeben des "Input:" und "Output:", warum das Script als "wrong answer" angegeben wird, wenn doch genau das ausgegeben wird, was gewünscht ist?

edit:

Habe es jetzt mal so umgebaut, dass das Sieb einmal erstellt wird und dann nur der entsprechende Bereich ausgegeben wird, nur sobald ich das Maximum auf den gewünschten Bereich erweitere, dann läuft das Script so ungemein langsam, dass es nie und nimmer bei SPOJ durchkommen würde. Ich bin ratlos.

Code: Alles auswählen

from math import sqrt

import psyco
psyco.full()

def sieve(m,n):
    sieve = range(n+1)
    sieve[1] = 0
    
    max_divider = int(sqrt(n))
    curr_divider = 2
    
    while curr_divider <= max_divider:
        lst_index = curr_divider**2
        while lst_index <= n:
            sieve[lst_index] = 0
            lst_index += curr_divider
        curr_divider += 1
        while sieve[curr_divider] == 0:
            curr_divider += 1
    
    return sieve

def get_answer():
    x = int(raw_input())
    answer = []
    for i in range(0,x):
        x = raw_input()
        y = x.split()
        answer.append(y)
    return answer

sieve = sieve(1,100000000)
answer = get_answer()

for i in answer:
    try:
        m = int(i[0])
        n = int(i[1])
        for i in range(m,n+1):
            if sieve[i] != 0:
                print sieve[i]
        print ''
    except:
        pass
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Donnerstag 5. Februar 2009, 15:43

BlackJack hat geschrieben:@numerix: Dumme Frage, aber wie berechne ich die Primzahlen von sagen wir mal 3000000 bis 4000000 ohne die vor 3000000 zu kennen. Mal von probalistischen Tests abgesehen?

Edit: Es gibt auf jeden Fall Python-Lösungen: https://www.spoj.pl/ranks/PRIME1/lang=PYTH
Die existierenden Python-Lösungen müssen dann einen entsprechend hochwertigen Algorithmus haben ...
Außerdem können die dort genannten Zeiten (deutlich unter 1 Sekunde) doch wohl die Zeit für die geforderte Ausgabe nicht mit enthalten ???
Weiterhin muss doch für einen Zeitenvergleich immer die gleiche Vorgabe an Zahlen gemacht werden. Das müssen doch dann in der Summe deutlich weniger als die theoretisch möglichen 1 Mio sein. ????

Zur ersten Frage: Zwar würde es genügen, zur Bestimmung der Primzahlen zwischen 3 Mio und 4 Mio alle Primzahlen bis 2000 zu kennen und auf Teilbarkeit zu prüfen, aber kennen MUSS ich sie dafür nicht, und *alle* Primzahlen kleiner als 3 Mio. schon gar nicht. Man kann ja auch die Teilbarkeit auf Zahlen prüfen, die keine Primzahlen sind, auch wenn das - wenn man die Primzahlen wüsste - nicht nötig wäre. Kennt man die Primzahlen nicht, prüft man z.B. alle ungeraden Zahlen auf Teilbarkeit. Wäre dann abzuwägen, was "billiger" zu haben ist.

Da es ja nicht nur darum geht, *eine* große Zahl als Primzahl zu identifizieren - dann würde ich es bei ungeraden Zahlen belassen -, sondern viele aufeinanderfolgende Zahlen, ist es vielleicht nicht der schlechteste (aber gewiss nicht der optimale) Weg, zunächst einmal alle Primzahlen bis 31607 (das sind - wenn man die 2 gleich weglässt - 3400 an der Zahl) zu ermitteln und in einer Liste abzulegen (das geht in der Tat sehr schnell), die man dann für die eigentliche Primzahlprüfung verwendet.

Mal sehen, vielleicht versuche ich ja mal eine Lösung ...
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Donnerstag 5. Februar 2009, 21:34

numerix hat geschrieben:Mal sehen, vielleicht versuche ich ja mal eine Lösung ...
Mit psycho sind die 6 Sekunden auf jeden Fall auch mit einem wenig ausgefeilten Algorithmus zu knacken, ohne Psycho hängt es von den dann konkret gegebenen Testzahlen und der Hardware ab. So wie ich die Aufgabenstellung verstanden habe, erfährt man die Testzahlen nicht.

Mein Algorithmus benötigt für die Überprüfung des Intervalls von 999.900.000 bis 1.000.000.000 - das ist für die Aufgabenstellung der worst case - bzw. die Ermittlung der darin enthaltenen 4832 Primzahlen mit psyco etwas mehr als 1 Sekunde (auf einem knapp 8 Jahre alten PC).
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Freitag 6. Februar 2009, 08:29

Mit welchen Mitteln hast du es geschafft, dass dir das Sieb dann keinen ``MemoryError`` ausgibt? Mit ``range`` bekomm ich diesen sofort, mit ``xrange`` nur etwas später, wobei ich bei xrange das aktuell mit einer Schleife in eine Liste schreibe.
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 6. Februar 2009, 11:30

Graf Wasserrutsche hat geschrieben:Mit welchen Mitteln hast du es geschafft, dass dir das Sieb dann keinen ``MemoryError`` ausgibt?
Indem ich kein "Sieb" benutze. Die Grundidee habe ich in meinem vorigen Post dargelegt - so habe ich es dann auch gemacht. Die Ermittlung *aller* Primzahlen bis 1 Mrd. *kann* nicht der richtige Weg sein. Das dauert einfach viel zu lange. Und dein Sieb läuft noch nicht mal bis 1 Mrd., sondern nur bis 100 Mio ....
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Freitag 6. Februar 2009, 14:16

Interessanter Link ueber Primzahlen.

http://tupac.euv-frankfurt-o.de/www/kryptos/prim.html

Habe selbst mal den Trial Division Algorithmus zur Primfaktorisierung implementiert.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 6. Februar 2009, 14:36

hendrikS hat geschrieben:Interessanter Link ueber Primzahlen.

http://tupac.euv-frankfurt-o.de/www/kryptos/prim.html

Habe selbst mal den Trial Division Algorithmus zur Primfaktorisierung implementiert.
Der "Trial Division Algorithmus" (das ist wohl eine Sprachschöpfung des Verfassers des von dir verlinkten Beitrags) ist das übliche Standardverfahren zur Primzahlprüfung, was im Grunde nichts anderes macht als zu prüfen, ob eine Zahl die Definiton für eine Primzahl erfüllt. Das entspricht dem, was ich oben schon gepostet habe.

Mein weiterer Vorschlag ist in etwa das, was der Verfasser als "Trial+" bezeichnet, nämlich eine Optimierung im Hinblick auf die konkrete Aufgabenstellung, die in diesem Fall eben auch verhältnismäßig große Primzahlen beeinhalten kann. Also berechnet man sich zunächst einen Basissatz an Primzahlen - für die konkrete Aufgabenstellung benötigt man alle Primzahl bis 31.607 -, so dass man sich in der Folge darauf beschränken kann, als Teiler der zu prüfenden Zahl nur noch auf Primfaktoren zu untersuchen.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Donnerstag 12. Februar 2009, 18:25

numerix hat geschrieben:Mal sehen, vielleicht versuche ich ja mal eine Lösung ...
Ausnahmsweise will ich mich mal selbst zitieren ... :oops:

Die SPOJ-Primzahlaufgabe hatte es mir angetan. Nachdem ich zunächst gar nicht glauben wollte, dass die Aufgabe mit Python überhaupt in der maximal vorgebenen Laufzeit von 6 s schaffbar sei - immerhin geht es hier um die Berechnung einiger 10.000 Primzahlen aus Intervallen der Größe 100.000 im Zahlbereich bis 1 Mrd. - hat BlackJack ja einen Link gepostet, der zu den schnellsten Python-Lösungen führt und da konnte man bestaunen, dass es tatsächlich möglich ist, ein Python-Programm zu schreiben, dass das Problem in 0.41 s löst! *Konnte* wohlgemerkt, denn jetzt gibt es ein noch schnelleres, und das ist meins - :D :
https://www.spoj.pl/ranks/PRIME1/lang=PYTH

Abgesehen davon, dass man überhaupt in diese zeitlichen Bereiche vorstoßen kann, war für mich das erstaunlichste daran, dass sich die Lösung (jedenfalls meine - die der anderen kenne ich ja nicht) nicht durch einen furchtbar komplexen Algorithmus auszeichnet, sondern durch einen intelligenten Einsatz des Siebes des Eratothenes. Der Kern-Algorithmus umfasst gerade einmal 10 Zeilen Code.

Zunächst dachte ich, man bräuchte irgendeinen hochspezialisierten Expertenalgorithmus und nach einigem googeln und wikipedieren findet man solche natürlich auch. Die waren mir aber allesamt so kompliziert, dass ich keine Lust hatte, mich da ernsthaft hineinzudenken. Stattdessen habe ich einige Stunden mit Papier und Bleistift zugebracht und mit dem mehr als 2000 Jahre alten Sieb des Eratothenes experimentiert.

Damit gelingt ein Programm mit einer Laufzeit deutlich unter 1 Sekunde, das ca. 30-40 Zeilen lang ist. Für die letzten Hunderstel Sekunden muss man dann natürlich noch ein Weilchen basteln und verschiedene - scheinbar gleichwertige, aber eben unterschiedlich performante - Varianten einzelner Teile ausprobieren.

Dank an Graf Wasserrutsche: Hat Spaß gemacht!
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Donnerstag 12. Februar 2009, 19:00

Respekt...! Da muss ich mich wohl auch noch mal ransetzen :wink:
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 13. Februar 2009, 01:59

Wow, gratuliere numerix - tolle Sache. Leider gibt es die Quellcodes nirgendwo öffentlich, was aber auch irgendwie verständlich ist.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Graf Wasserrutsche
User
Beiträge: 37
Registriert: Donnerstag 17. Juli 2008, 06:59
Wohnort: Köln
Kontaktdaten:

Freitag 13. Februar 2009, 08:35

Gratulation! Bei mir wirds dann glaube ich noch ein ganzes Weilchen dauern :)
[url=http://myspace.com/deathmetalvictory][myspace][/url][url=http://grunzgewitter.blogspot.com][blog][/url][url=http://twitter.com/AgatheBauer][twitter][/url]
Antworten