Primzahlen + Sieb des Eratosthenes

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Tompee
User
Beiträge: 18
Registriert: Sonntag 7. Oktober 2007, 17:13

Sonntag 25. November 2007, 16:40

Hi,

ich beschäftige mich gerade mit einem Algorithmus zur Bestimmung der Primzahlen bis zur einer bestimmten Zahl.
Als Vorlage hab ich diese Seite genommen:http://www-i1.informatik.rwth-aachen.de ... algo25.php

Aber irgendwie läuft das ganze bei mir zu langsam ab. Ich komme nicht mal ungefähr an die Zeiten, die dort auf der Seite stehen.

Meine Frage ist nun, ob es an Python liegt oder ob bei meinem Code etwas nicht stimmt.

Meine Zeiten bei 10^4 liegt bei ca. 2,5 s und bei 10^5 ca. 250 s.(Intel Q6600) :shock:

Code: Alles auswählen

#!/usr/bin/env python

from time import time

def prime(n):

    primes = range(2, n + 1)
    
    for x in xrange(2, int(n ** .5) + 1):
        
        if x in primes:
        
            for y in xrange (n  /  x , x - 1, -1):
            
                if y in primes:
                    
                    tmp = x * y
                   
                    if tmp in primes:
                
                        primes.remove(tmp)
                
    primes.sort()
    return primes


a = time()
prime(100000)
b = time()

print str(b - a) + ' Sekunden'
Gruss Tompee
Zuletzt geändert von Tompee am Sonntag 25. November 2007, 19:00, insgesamt 1-mal geändert.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Sonntag 25. November 2007, 17:56

Dein Problem ist, dass sowohl die Suche mit "in" als auch das "remove" in Listen lineare Laufzeit haben. Nimm für die Primzahl"liste" lieber ein Dictionary.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
BlackJack

Sonntag 25. November 2007, 18:30

Man kann auch bei Liste bleiben und sich klarmachen, dass eine Zahl zu streichen nicht gleichbedeutend ist, mit einen Eintrag aus der Liste zu entfernen. Und die Zahlen selbst müssen auch nicht in der Liste stehen weil sie ja im Grunde schon durch den Index angegeben sind.
Tompee
User
Beiträge: 18
Registriert: Sonntag 7. Oktober 2007, 17:13

Sonntag 25. November 2007, 18:46

Danke euch, werde mich darum kümmern.

Nachtrag:

Habe es jetzt erstmal so gemacht:

Code: Alles auswählen

#!/usr/bin/env python

from time import time

def prime(n):

    primes = {}
    
    for i in xrange(2, n + 1):
        
        primes[i] = True
   
    for x in xrange(2, int(n ** .5) + 1):
       
        if primes[x] == True:
       
            for y in xrange (n / x  , x -1, -1):
           
                if primes[y] == True:
                   
                    tmp = x * y
                   
                    if tmp in primes:
               
                        primes[tmp] = False
               
    return primes


a = time()
prime(100000)
b = time()
Die Zeiten sind schon schneller(10^4 0,016s und 10^5 0,266 s).
Ab 10^8 gibt es aber Speicherprobleme. Es kommt dann beim ausführen immer MemoryError.

Gruss Tompee
Zuletzt geändert von Tompee am Dienstag 27. November 2007, 17:40, insgesamt 1-mal geändert.
BlackJack

Sonntag 25. November 2007, 20:13

Den Test in Zeile 23 kannst Du Dir sparen.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Sonntag 25. November 2007, 21:54

Man könnte auch über ein Set statt des Dicts nachdenken.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Tompee
User
Beiträge: 18
Registriert: Sonntag 7. Oktober 2007, 17:13

Sonntag 25. November 2007, 22:28

Mit Sets habe ich mich noch nicht beschäftigt, werd ich mir mal anschauen.
Bin noch nicht so lang dabei.

Das Problem bei dieser Methode ist, dass ich am Anfang immer eine Liste, Dict oder eben ein Set erstellen muss, was erstmal alle Zahlen enthält, bis zu der ich die Primzahlen ermitteln möchte. Und ab 10^8 wird dem Rechner das zuviel. Ich werde das zwar so wahrscheinlich nie brauchen, aber es stört mich irgendwie.


Gruss Tompee
BlackJack

Montag 26. November 2007, 09:22

Wenn man nur 8 Byte pro Zahl ansetzt, sind das ja auch schon ca. 763 MiB. Das wären auf einem 64-Bit-Rechner nur die nackten Zahlen, dazu käme dann noch ein wenig Verwaltungsinformation pro `int`-Objekt und ein(e) Liste/Dict/Set mit Referenzen auf die ganzen Objekte.

Ein "Trick" ist wie gesagt eine Liste zu benutzen und die Zahlen selbst gar nicht zu speichern, sondern nur `True` und `False` ob die Zahl, die dem Index entspricht, nun eine Primzahl ist oder nicht.

Weiter Speicherplatz einsparen könnte man dann noch mit `array.array()` und dort dann nur ein Byte pro Zahl speichern, oder man arbeitet mit einem Bitset; da dürfte das drumherum des Bitsets in Python geschrieben allerdings die Geschwindigkeit einbrechen lassen.

Oh, und man könnte noch auf Festplatte ausweichen und eine groooooooosse Datei mit dem `mmap`-Modul verwenden.
BlackJack

Montag 26. November 2007, 12:35

Hm, irgendwie bin ich zu blöd ─ ich verstehe den letzten, verbesserten Algorithmus nicht. Kann es sein dass die nur Multiplikationen zählen und so unwichtige Sachen wie den "enthalten sein"- und "ist das schon eine Primzahl"-Test ignorieren? Oder anders gefragt, wie sähe die verbesserte Version zu folgendem normalen Sieve aus!?

Code: Alles auswählen

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N   (100000000)

char primes[N];


static void print_primes(void)
{
    int i;
    
    for (i = 2; i < N; i++) {
        if (primes[i]) printf("%d\n", i);
    }
}


static void prepare(void)
{
    memset(primes, 1, N);
    primes[0] = primes[1] = 0;
}


static void sieve(void)
{
    int i, k;

    prepare();
    for (i = 2; i < sqrt(N); i++) {
        if (primes[i]) {
            for (k = 2 * i; k < N; k += i) {
                primes[k] = 0;
            }
        }
    }
}


int main(void)
{
    sieve();
    /* print_primes(); */
    return 0;
}
Antworten