100までの整数から素数を列挙せよ(SQL編)

キミならどう書く 2.0 – ROUND 1 –

「欲しいものを書くだけでいい」というのがSQLのいいところ。この場合は「約数をちょうど2つ持つ整数」と書けばいい。エラトステネスの篩いを試みたりしてはいけない。(そういう意味ではPrologでもいいのだけれど、文法を思い出せない。)

-- 0から9までの数を入れるテーブル
create table nums (i integer);

-- 0から9までの数を入れる
insert into nums (i) values (0), (1), (2), (3), (4), (5), (6), (7), (8), (9);

-- 0から99までの数を入れるテーブル(100は素数でない)
drop table if exists integers;
create table integers
  select 10*a.i+b.i as n
  from nums as a, nums as b
  order by n;

-- 素数を表示する
select n prime from(
  select x.n, count(distinct d.n) c
  from integers x,integers d
  where mod(x.n,d.n)=0 and d.n<=x.n
  group by x.n) tmp
where c=2
order by prime;

以上


以下は古いバージョン(いろいろやりすぎ)。

SELECT n prime FROM(
  SELECT x.n,COUNT(DISTINCT d.n) c
    FROM integers x,integers d
    WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
    GROUP BY x.n) tmp
  WHERE c=2;

あらかじめ整数をテーブルに入れておくという準備が必要で、Oracleならこんな感じか。

DROP TABLE integers;
CREATE TABLE integers (n INT NOT NULL);

DECLARE
  maxNum INT:=100;
  i INT:=1;
BEGIN
  EXECUTE IMMEDIATE 'TRUNCATE TABLE integers';
  WHILE i<maxNum LOOP
    INSERT INTO integers (n) VALUES (i);
    i:=i+1;
  END LOOP;
END;
/
SELECT n prime FROM(
  SELECT x.n,COUNT(DISTINCT d.n) c
    FROM integers x,integers d
    WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
    GROUP BY x.n) tmp
  WHERE c=2;

SELECT文を直接書けないからPL/SQLはあまり好きではないんだけど、
無理矢理PROCEDUREにするなら、こんな感じか。

CREATE OR REPLACE PROCEDURE primes (maxNum INT) AS
  i INT:=1;
  CURSOR cur IS
    SELECT n prime FROM(
      SELECT x.n,COUNT(DISTINCT d.n) c
        FROM integers x,integers d
        WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
        GROUP BY x.n) tmp
      WHERE c=2;
BEGIN
  EXECUTE IMMEDIATE 'TRUNCATE TABLE integers';
  WHILE i<maxNum LOOP
    INSERT INTO integers (n) VALUES (i);
    i:=i+1;
  END LOOP;
  
  FOR item IN cur
  LOOP
    DBMS_OUTPUT.PUT_LINE(item.prime);
  END LOOP;
END;
/
CALL primes(100);

Version 5になってやっと使えるようになったMySQLのストアド・プロシージャを使うなら。

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (n INT)//

DROP PROCEDURE IF EXISTS primes//
CREATE PROCEDURE primes(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  TRUNCATE table integers;
  WHILE i<maxNum DO
    INSERT INTO integers (n) VALUES (i);
    SET i=i+1;
  END WHILE;
  
  SELECT n prime FROM(
    SELECT x.n,COUNT(DISTINCT d.n) c
      FROM integers x,integers d
      WHERE MOD(x.n,d.n)=0 AND d.n<=x.n
      GROUP BY x.n) tmp
    WHERE c=2;
END;//

CALL primes(100)//

追記:エラトステネスの篩いね、そりゃあ、このほうが速いよ。

DELIMITER //
DROP TABLE IF EXISTS integers//
CREATE TABLE integers (
  n INT PRIMARY KEY,
  flag INT DEFAULT 0 NOT NULL,
  KEY(flag)
)//

DROP TABLE IF EXISTS results//
CREATE TABLE results (prime INT PRIMARY KEY)//

DROP PROCEDURE IF EXISTS primes//
CREATE PROCEDURE primes(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 2;
  TRUNCATE table integers;
  WHILE i<maxNum DO
    INSERT INTO integers (n) VALUES (i);
    SET i=i+1;
  END WHILE;
  
  WHILE EXISTS (SELECT * FROM integers WHERE flag=0) DO
    INSERT INTO results (prime) SELECT n FROM integers WHERE flag=0 LIMIT 1;
    UPDATE integers JOIN (SELECT MAX(prime) p FROM results) tmp SET flag=1 WHERE MOD(n,p)=0;
  END WHILE;
  
  SELECT prime FROM results;
END;//

CALL primes(100)//

2 thoughts on “100までの整数から素数を列挙せよ(SQL編)

  1. タイトルのとおり、「100までの素数を列記する方法」です

コメントは停止中です。