SQL 找出 100 以内的质数

zero

关注

发布于: 2020 年 05 月 19 日

上一篇写的是 SQL 生成斐波那契数列 ，今天就来实现使用 SQL 获取 100 以内的质数。

先来看下质数的定义（以下定义摘选自百度百科）：

质数又称素数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

判断一个大于 2 的正整数是否是质数，通常使用的算法是：

假设该数是 n，用 2 到 $n$ 的数去整除 n，如果能被整除，则说明 n 是合数，否则该数是质数。

那具体到 SQL 里该怎么实现呢？

第 1 步，生成 2 - 100 的自然数列

如果你已经有了一张数字辅助表，那么可以从这张辅助表中获取 2 - 100 的自然数列。如果什么都没有，则使用下面的脚本就能生成 2 - 100 的数。

WITH recursive seq (num) AS (SELECT   2 AS num UNIONALL SELECT   num + 1 AS num FROM  seq WHERE num < 100) SELECT   * FROM  seq

复制代码

上面这段 SQL 在 MySQL 8.0+ 的版本上可以运行，如果使用其它数据库，只要支持 CTE 语法，稍微改下就能运行。

第 2 步，找到质数

假如我们要判断 seq 表中的 31 是不是质数，只需检查 seq 表中从 2 - 5（ $⌊ 31 ⌋$ ）可以整除 31 的有多少个，如果一个也没有，则说明 31 是质数。对应的 SQL 可以这么写：

SELECT   num AS prime FROM  seq a WHERE 0 >=   (SELECT     COUNT(*)   FROM    seq b   WHERE b.num <= SQRT(a.num)     AND a.num % b.num = 0)

复制代码

如果觉得 0 > = (SELECT COUNT(*) ...) 这种写法不好理解，也可以改写成 NOT EXISTS 的写法，完整的 SQL 如下：

WITH recursive seq (num) AS (SELECT   2 AS num UNIONALL SELECT   num + 1 AS num FROM  seq WHERE num < 100) SELECT   num AS prime FROM  seq a WHERE NOT EXISTS  (SELECT     NULL  FROM    seq b   WHERE b.num <= SQRT(a.num)     AND a.num % b.num = 0)

复制代码

打印出来的结果：

 prime  --------       2       3       5       7      ...      ...      89      97

复制代码

100 以内总共有 25 个质数，限于篇幅，省略了中间的部分数据。

发布于: 2020 年 05 月 19 日阅读数: 118

zero

关注

以终为始，不忘初心。 2018.04.26 加入

SQL 写得贼溜，对 SQL 感兴趣的可以关注我的公众号【SQL实现】。

发布

暂无评论

创作场景

SQL 找出 100 以内的质数

zero

评论