首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >SQL 找出 100 以内的质数

SQL 找出 100 以内的质数

作者头像
白日梦想家
发布2020-07-20 10:33:55
1.3K0
发布2020-07-20 10:33:55
举报
文章被收录于专栏:SQL实现SQL实现

之前我写了一篇文章 SQL 生成斐波那契数列,在原来的基础上,今天就来实现使用 SQL 获取 100 以内的质数。

先来看下质数的定义(以下定义摘选自百度百科):

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

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

假设该数是 n,用 2 到

的数去整除 n,如果能被整除,则说明 n 是合数,否则该数是质数。

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

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

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

WITH recursive seq (num) AS 
(SELECT 
  2 AS num 
UNION
ALL 
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 是质数。对应的 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 
UNION
ALL 
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,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 SQL实现 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 MySQL
腾讯云数据库 MySQL(TencentDB for MySQL)为用户提供安全可靠,性能卓越、易于维护的企业级云数据库服务。其具备6大企业级特性,包括企业级定制内核、企业级高可用、企业级高可靠、企业级安全、企业级扩展以及企业级智能运维。通过使用腾讯云数据库 MySQL,可实现分钟级别的数据库部署、弹性扩展以及全自动化的运维管理,不仅经济实惠,而且稳定可靠,易于运维。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档