Primzahlen + Sieb des Eratosthenes

[Tompee]

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)

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

[birkenfeld]

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.

[BlackJack]

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]

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

[BlackJack]

Den Test in Zeile 23 kannst Du Dir sparen.

[birkenfeld]

Man könnte auch über ein Set statt des Dicts nachdenken.

[Tompee]

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]

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]

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;
}