求素数个数

我最近在leetcode上撸了一个小算法,虽然已经工作了五年,当看到每次代码提交后排名的提升,内心依然很有成就感。题目比较简单,求小于n的素数个数,素数也叫质数,具有以下特点:

  • 正整数
  • 只能被1和本身整除
  • 1既不是素数也不是合数,所以最小的素数是2

根据上面的特点,我们还可以推断出:

  • 除了2,其它的素数都是奇数

依据这一点,我们可以写出下面的实现:

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = 1;// 2
        for (int i = 3; i < n; i += 2) {
            // 只判断奇数是不是素数
            boolean isPrime = true;
            for (int j = 3; j * j <= i; j += 2) {
                // 奇数不可能被偶数整除,所以只试除奇数
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                count++;
            }
        }
        return count;
    }
}

j * j <= i相当于j <= Math.sqrt(i),但速度会快一点,那为什么只需要判断到√i呢,因为对于一个非素数(合数),其最小约数(除1外)必小于等于其平方根。

这个实现被Accept了,但时间复杂度较高,排名也很靠后。这个算法中,判断一个奇数i是不是素数,是通过试除小于等于√i的奇数来实现,这会有重复计算的场景,比如3和9,5和15,根据素数和合数的特点,可以推断出任意一个合数都可以分解成几个素数的乘机,所以我们可以通过试除小于等于√i的素数来判断i是不是素数,素数相对于奇数,无疑减少了很多判断次数。

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = 0;
        int[] primes = new int[n / 2];
        for (int i = 3; i < n; i += 2) {
            // 只判断奇数是不是素数
            boolean isPrime = true;
            for (int j = 0; j < count && primes[j] * primes[j] <= i; j++) {
                // 只试除素数
                if (i % primes[j] == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes[count++] = i;
            }
        }
        return count + 1;// 2
    }
}

效果好了一些,但这个实现时间复杂度依然很高,比试除法更高效的是筛选法,筛选法的策略是将素数的倍数全部筛掉,剩下的就是素数了,下图很生动的体现了筛选的过程:

筛选的过程是先筛掉非素数,针对本文的题目,每筛掉一个,素数数量-1即可,上面说过素数的一个特点,除了2,其它的素数都是奇数,所以我们只需在奇数范围内筛选就可以了。

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = n / 2;// 筛掉一半偶数
        boolean[] notPrime = new boolean[n];
        for (int i = 3; i * i < n; i += 2) {// 只筛3≤i<√n奇数
            if (!notPrime[i]) {        
                // 筛掉素数的奇数倍数
                for (int j = i * i; j < n; j += 2 * i) {// 从i*i开始筛
                    if (!notPrime[j]) {
                        notPrime[j] = true;
                        count--;
                    }
                }
            }
        }
        return count;
    }
}

示例

3

5

7

9

11

13

15

17

19

21

23

25

27

29

备注

i=3

3

5

7

9

11

13

15

17

19

21

23

25

27

29

3->9,15,21,27

i=5

3

5

7

9

11

13

15

17

19

21

23

25

27

29

5->25

对于一个奇数i,会依次筛掉i*i,i(i+2),i(i+4),i(i+6)…i(i+2n),那么为什么不筛3i,5i,7i…(i-4)i,(i-2)i呢,因为他们已经被筛过了,当我们要筛掉奇数i的倍数时,那么i之前的奇数(i-2,i-4…7,5,3)的倍数((i-2)i,(i-4)i…7i,5i,3i)已经被筛掉了,这个算法的效果还不错。

版权声明 本博客所有的原创文章,作者皆保留版权。转载必须包含本声明,保持本文完整,并以超链接形式注明作者高爽

我的博客在腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏顶级程序员

总算搞清楚了回车和换行的来历与区别

总算搞清楚”回车”(carriage return)和”换行”(line feed)这两个概念的来历和区别了。 在计算机还没有出现之前,有一种叫做电传打字机(...

2845
来自专栏CoXie带你学编程

初学Python:写码时应该缩进使用 tab 还是空格?

在不同的编辑器里tab的长度可能不一致,所以在一个编辑器里用tab设置缩进后,在其它编辑器里看可能缩进就乱了。空格不会出现这个问题,因为空格就占一个字符的位置。

981
来自专栏null的专栏

算法类面试题解析——美团2016校招:最大差值

题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。 ? 分析: 基本方法是遍历数组,找到当前值前面所有数组元素的最小值。 方法: int get_max_di...

3065
来自专栏计算机视觉与深度学习基础

模拟猜单词游戏

模拟实现猜单词游戏,纯模拟,不涉及图形界面,注释很详细,虽然本人代码写得丑,但是希望可以给大家提供帮助 #include<algorithm> #include...

18210
来自专栏数据结构与算法

BZOJ5312: 冒险(势能均摊线段树)

结论:如果一次操作对区间& 和 区间| 产生的影响是相同的,那么该操作对整个区间的影响都是相同的

482
来自专栏机器学习入门

LWC 55:713. Subarray Product Less Than K

LWC 55:713. Subarray Product Less Than K 传送门:713. Subarray Product Less Than K P...

2025
来自专栏数据结构与算法

2017 清北学堂 Day 6终极考试报告

预计分数: 100+70+70 = 240 实际假分数 : 40+80+70= 190  in cena(好吧不得不承认这个分数,,,,,,=.=) 实际真分数...

2903
来自专栏Sign

web版《合成10》制作过程

《合成10》是一个很容易上瘾的游戏。 之前尝试的写了个网页版,游戏地址 ccx01.com/game/get10/ 现在写一下网页版合成10的制作过程。 这个游...

31912
来自专栏编程

正则表达式游戏的答案

两天过去了,我们才送出了四个番茄钟(其中一个还是作为礼物送给了鲁鸿驹先生,感谢鲁鸿驹的现场莅临指导 ,鲁总是VIM的fans,多年不编程的他还记得是删除一行的指...

2018
来自专栏林德熙的博客

C# 判断文件编码

我们的项目中会包含有很多文件,但是可能我们没有注意到的,我们的文件的编码不一定是utf-8,所以可能在别人电脑运行时出现乱码。最近在做一个项目,这个项目可以把我...

1362

扫码关注云+社区