Sieb des Eratosthenes in SQL mittels doppeltem JOIN

[Philipp Schafft <lion@xxxxxxxxx>]

flum ihr,

gestern Arbent hat mir einer nen altes Stueckschen Perl von mir gezeigt,
nen Sieb des Eratosthenes[0], das Primzahlen[1] sucht. Da ich garde ne
SQL Shell vor mir hatte habe ich mal kurtz ueberlegt ob loewe das
mittels eines Joins loesen koennte.

Und tatsache, nach etwar 5 min hatte ich meine erste Loesung (diese habe
ich seither noch net erneut ueberdacht, aber ggf. hat ja wer lust). Hier
etwas SQL:

-- Tabelle mit Zahlen anlegen:
CREATE TABLE nums (i INT NOT NULL PRIMARY KEY);
\! seq 1 128 > /tmp/seq
\copy nums FROM /tmp/seq

-- ein View erzeugen welches das filtern uebernimmt:
CREATE VIEW primes AS SELECT a.i AS "Prime" FROM nums AS a, nums AS b, nums as c WHERE b.i <= a.i AND c.i <= a.i AND a.i != b.i * c.i GROUP BY a.i HAVING COUNT(*) = POW(a.i,2)-2;


Nun ist die Sache bereit, das View beinhaltet alle Primzahlen:
\timing
SELECT * FROM primes;
 Prime
-------
     2
     3
     5
     7
...
(31 rows)
Time: 397.302 ms


Jeder Zahl wird im obigen einzeln getestet, was neben dem Nachteil der
Rechenzeit auch vorteile hat:
SELECT * FROM primes WHERE "Prime" = 127;
 Prime
-------
   127
(1 row)
Time: 7.885 ms

SELECT * FROM primes WHERE "Prime" = 126;
 Prime
-------
(0 rows)
Time: 7.892 ms

Primzahlen lassen sich so schoen Einzeln testen.

Natuerlich auch Ranges:
SELECT * FROM primes WHERE "Prime" > 24 AND "Prime" < 32;
 Prime
-------
    29
    31
(2 rows)
Time: 6.214 ms

Oder die suche nach Mersenne-Primzahlen[2]:
SELECT * FROM primes WHERE ABS(LN("Prime" + 1)/LN(2) - dtrunc(LN("Prime" + 1)/LN(2))) < 0.001;
 Prime
-------
     3
     7
    31
   127
(4 rows)
Time: 13.542 ms

Vielliecht hatte ja jetzt jemand Sparss an meinen ausfuerungen.

Zum schluss mag noch verweisen sein auf primes(6) das wesentlich
schneller ist ;)

[0] http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
[1] http://de.wikipedia.org/wiki/Primzahl
[2] http://de.wikipedia.org/wiki/Mersenne-Primzahl

-- 
Philipp.
 (Rah of PH2)
-- 
UUGRN e.V. http://www.uugrn.org/
http://mailman.uugrn.org/mailman/listinfo/uugrn
Wiki: https://wiki.uugrn.org/UUGRN:Mailingliste
Archiv: http://lists.uugrn.org/