专栏首页Java那些事如何用算法高效寻找素数?

如何用算法高效寻找素数?

预计阅读时间:5 分钟

素数的定义很简单,如果一个数如果只能被 1 和它本身整除,那么这个数就是素数。

不要觉得素数的定义简单,恐怕没多少人真的能把素数相关的算法写得高效。本文就主要聊这样一个函数:

// 返回区间 [2, n) 中有几个素数 
int countPrimes(int n)

// 比如 countPrimes(10) 返回 4
// 因为 2,3,5,7 是素数

你会如何写这个函数?当然可以这样写:

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim(i)) count++;
    return count;
}

// 判断整数 n 是否是素数
boolean isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            // 有其他整除因子
            return false;
    return true;
}

这样写的话时间复杂度 O(n^2),问题很大。首先你用 isPrime 函数来辅助的思路就不够高效;而且就算你要用 isPrime 函数,这样实现也是存在计算冗余的

先来简单说下如果你要判断一个数是不是素数,应该如何写算法。只需稍微修改一下上面的 isPrime 代码中的 for 循环条件:

boolean isPrime(int n) {
    for (int i = 2; i * i <= n; i++)
        ...
}

换句话说,i不需要遍历到n,而只需要到sqrt(n)即可。为什么呢,我们举个例子,假设n = 12

12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2

可以看到,后两个乘积就是前面两个反过来,反转的分界点就在sqrt(n)

换句话说,如果在[2,sqrt(n)]这个区间之内没有发现可整除因子,就可以直接断定n是素数了,因为在区间[sqrt(n),n]也一定不会发现可整除因子。

这样,isPrime函数的时间复杂度降为了 O(sqrt(N)),但是我们实现countPrimes函数其实并不需要这个函数,以上只是希望读者明白sqrt(n)的含义,因为等会还会用到。

高效实现 countPrimes

高效解决这个问题的核心思路是和上面的常规思路反着来:

首先从 2 开始,我们知道 2 是一个素数,那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。

然后我们发现 3 也是素数,那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。

看到这里,你是否有点明白这个排除法的逻辑了呢?先看我们的第一版代码:

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    // 将数组都初始化为 true
    Arrays.fill(isPrim, true);

    for (int i = 2; i < n; i++) 
        if (isPrim[i]) 
            // i 的倍数不可能是素数了
            for (int j = 2 * i; j < n; j += i) 
                    isPrim[j] = false;

    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;

    return count;
}

图片来自 Wikimedia

如果上面这段代码你能够理解,那么你已经掌握了整体思路,但是还有两个细微的地方可以优化。

首先,回想刚才判断一个数是否是素数的isPrime函数,由于因子的对称性,其中的 for 循环只需要遍历[2,sqrt(n)]就够了。这里也是类似的,我们外层的 for 循环也只需要遍历到sqrt(n)

for (int i = 2; i * i < n; i++) 
    if (isPrim[i]) 
        ...

除此之外,很难注意到内层的 for 循环也可以优化。我们之前的做法是:

for (int j = 2 * i; j < n; j += i) 
    isPrim[j] = false;

这样可以把i的整数倍都标记为false,但是仍然存在计算冗余。

比如i = 4时算法会标记 4 × 2 = 8,4 × 3 = 12 等等数字,但是 8 和 12 已经被i = 2i = 3的 2 × 4 和 3 × 4 标记过了。

我们可以稍微优化一下,让ji的平方开始遍历,而不是从2 * i开始:

for (int j = i * i; j < n; j += i) 
    isPrim[j] = false;

这样,素数计数的算法就高效实现了。其实这个算法有一个名字,叫做 Sieve of Eratosthenes。看下完整的最终代码:

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    Arrays.fill(isPrim, true);
    for (int i = 2; i * i < n; i++) 
        if (isPrim[i]) 
            for (int j = i * i; j < n; j += i) 
                isPrim[j] = false;

    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;

    return count;
}

该算法的时间复杂度比较难算,显然时间跟这个嵌套 for 循环有关,其操作数应该是:

n/2 + n/3 + n/5 + n/7 + … = n × (1/2 + 1/3 + 1/5 + 1/7…)

括号中是素数的倒数和。其最终结果是 O(N * loglogN),有兴趣的读者可以查一下该算法的时间复杂度证明。

以上就是素数算法相关的全部内容。怎么样,是不是看似简单的问题却有不少细节可以打磨呀?

反向思考方能出其不意!

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli),作者:labuladong

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法专题:如何用算法高效寻找素数?

    不要觉得素数的定义简单,恐怕没多少人真的能把素数相关的算法写得高效。本文就主要聊这样一个函数:

    帅地
  • 五分钟小知识:如何用算法高效寻找素数?

    不要觉得素数的定义简单,恐怕没多少人真的能把素数相关的算法写得高效。本文就主要聊这样一个函数:

    五分钟学算法
  • 算法--排序--寻找数组内第K大的元素

    此题目,需要用到快速排序里的划分数组操作: 快排参考:https://blog.csdn.net/qq_21201267/article/details/81...

    Michael阿明
  • 如何使用「番茄法」高效的写算法题?

    在刷题的过程中非常最容易产生挫败感,无法坚持。原因是,长时间的思考导致疲倦,多次积累的疲倦使得自己产生了 抵触记忆。以至于会下意识觉得做题就是 刻苦。

    五分钟学算法
  • 如何找到属于自己高效学习方法?

    大家好,我是小鹿,一个学习方法的终生分享者。在进入今天的主题之前,我想讲讲我是如何成为一个喜欢分享学习方法和经历的人,这有利于你对我的一些经历和后续分享学习方法...

    不安分的猿人
  • 如何在Debian 7上使用wget命令寻找失效的链接

    您多少次点击网页上的HTML链接只是为了获得404 Not Found错误?存在断开的链接,因为网页有时会随时间移动或删除。网站管理员的工作是在人类网络访问者或...

    心语花束
  • 【机器学习算法系列】如何用Apriori寻找到繁杂数据之间的隐藏关系

    大型超市有海量交易数据,我们可以通过聚类算法寻找购买相似物品的人群,从而为特定人群提供更具个性化的服务。但是对于超市来讲,更有价值的是如何找出商品的隐藏关联,从...

    统计学家
  • 如何高效学习数据结构与算法《学习笔记》

    很多同学在大学的时候会觉得数据结构与算法很枯燥,很多小伙伴都不愿意听这门课程。甚至以前还觉得能开发一个项目就能成为一个合格的程序员。但是学会算法,或者接触过数据...

    三钻
  • 如何实现一个高效的启发式算法?

    小伙伴们好,说起来已经好久好久好久没见了呢!之前一直忙着做其他事情去了(泛指学习一类),公众号已经落下好久好久了。今天来写点好玩的东西。

    短短的路走走停停
  • 如何用人工智能从新型数据中来寻找Alpha

    作者 CDA 数据分析师 编者按 随着移动互联网,小型卫星普及等,资产管理公司,尤其对冲基金公司开始利用人工智能从新型数据中来寻找Alpha。 本期精编版嘉宾...

    CDA数据分析师
  • 拿来就能用!如何用 AI 算法提高安全运维效率?

    在整个安全工作中,安全运维是不可或缺的一环,其目的是保证各项安全工作持续有效地运作。除了对外的沟通和业务对接相关工作,大部分安全运维的日常工作相对固定,如漏洞审...

    AI科技大本营
  • 在一个千万级的数据库查寻中,如何提高查询效率?

    A. 对查询进行优化,应尽量避免全表扫描,首先应考虑在 where 及 order by 涉及的列上建立索引。

    Java后端技术
  • 在一个千万级的数据库查寻中,如何提高查询效率?

    1、对查询进行优化,应尽量避免全表扫描,首先应考虑在 where 及 orderby 涉及的列上建立索引;

    用户1655470
  • 如何实现一个高效的启发式算法?(VRPTW篇)

    上一期大家的反馈还不错,希望小编多多写写这种类似心得的文章。刚好小编最近也要学新东西了,打算把之前学的东西都整理一下写写,希望给大家带来一点小小的帮助吧~所以今...

    短短的路走走停停
  • PHP 如何获取 BiliBli 指定用户粉丝数量 寻找 API 地址

    前段时间刷13站看到了这个视频 av26280568 那么!要怎么获取呢? 首先咱们打开个人空间 (查看链接»),我们可以看到右下角有关注数和粉丝数 (少的可怜...

    叮当叮
  • 如何高效的使用PowerShell备份数据库

    初始脚本 Get-SqlDatabase -ServerInstance localhost | Where { $_.Name -ne 'tempdb' } ...

    用户1217611
  • 在Java中如何高效判断数组中是否包含某个元素

    原文地址:http://www.hollischuang.com/archives/1269

    Java后端技术
  • 蚁群算法详解

    如何寻找一条合适的路径,几乎是一个永恒的话题。每个人、每天都会遇到。大到全国列车的运行规划,小到每个人的手机导航。其中一部分是关于“如何寻找两个位置间的最短距离...

    智能算法
  • 教程 | 如何在TensorFlow中高效使用数据集

    机器之心

扫码关注云+社区

领取腾讯云代金券