SQLで素数サーチ

「割り切る数が存在しない」ことをEXISTS述語で表現する


自然数を，順序のない単なる数の集合として扱うところがいかにもSQLらしい．

import sqlite3

db = sqlite3.connect(":memory:");
c = db.cursor();

c.execute("CREATE TABLE Digits(n)");
c.executemany("INSERT INTO Digits VALUES(?)", [
    (0,), (1,), (2,), (3,), (4,), (5,), (6,), (7,), (8,), (9,),
]);

numbers = "SELECT D1.n + 10 * D2.n AS n \
             FROM Digits D1 CROSS JOIN Digits D2";
c.execute("CREATE VIEW Numbers AS " + numbers);

divisor = "(SELECT * \
              FROM Numbers Divisor \
             WHERE Divisor.n <= Dividend.n / 2 \

               AND Divisor.n != 1 \
               AND Dividend.n % Divisor.n = 0)";

primeNumber = "SELECT n AS primeNumber \
                 FROM Numbers Dividend \
                WHERE n > 1 \
                  AND NOT EXISTS " + divisor;

c.execute(primeNumber + "order by primeNumber");

for row in c:
    print(row);

c.close();
db.close();

Python だと１行で書けるけどな！

print([p for p in range(2, 100) if [1 for d in range(2, 1 + p // 2) if p % d == 0] == []]);