算法创作|质数计数问题解决方法

简介: 算法创作|质数计数问题解决方法

问题描述

统计所有小于非负整数n的质数的数量。

示例:

输入:n = 10

输出:4

示例:

输入:n = 1

输出:0

示例:

输入:n = 0

输出:0

提示:0 <= n <= 5 * 106


解决方案


对于每个数i我们可以枚举 [2, i-1][2i-1]区间的任意一个数j,判断i能否被j整除,枚举 [2, i-1][2,i−1] 区间的任意一个数j,判断i能否被j整除时,我们可以发现,如果i能够被j整除,那么这里的商也一定能够整除i,也就是i也能够被i/j整除。那么我们只要判断ii/j其中一个能否整除i即可。

代码清单 1统计所有小于非负整数n的质数的数量

class Solution:

    def countPrimes(self, n: int) -> int:

        def is_prime(num):

            j = 2

            while j * j <= num:

                if num % j == 0:

                    return False

                j += 1

            return True

        count = 0

        for i in range(2, n):

            if is_prime(i):

                count += 1

        return count

运行代码

 

结语

此类方法需要较为麻烦,思维较为复杂,需要单次判断每一个数是否为质数,淡然也可以采取枚举法、线性筛等方法,这些方法可能更容易理解,当我们遇到此类问题时,需迅速构建出各种方法,在这之中筛选,选出更简单的方法。




目录
相关文章
|
机器学习/深度学习 算法
【算法基础】筛质数
【算法基础】筛质数
68 0
|
存储 算法 程序员
【五一创作】C++程序设计与算法(一) 北京大学 郭炜(下)
【五一创作】C++程序设计与算法(一) 北京大学 郭炜(下)
60 0
|
算法 Java C语言
【五一创作】C++程序设计与算法(一) 北京大学 郭炜(上)
【五一创作】C++程序设计与算法(一) 北京大学 郭炜
98 0
|
7月前
|
算法
基于光流法的车辆检测计数算法matlab仿真,对比Horn-Schunck光流和Lucas-Kanade光流
基于光流法的车辆检测计数算法matlab仿真,对比Horn-Schunck光流和Lucas-Kanade光流
|
4月前
|
搜索推荐 算法
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
|
6月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
7月前
|
人工智能 算法 C++
c++算法学习笔记 (17) 质数
c++算法学习笔记 (17) 质数
|
6月前
|
算法 Java
Java数据结构与算法:冲突解决方法
Java数据结构与算法:冲突解决方法
|
7月前
|
算法
算法题解-计数质数
算法题解-计数质数
|
7月前
|
机器学习/深度学习 算法 vr&ar
☆打卡算法☆LeetCode 204. 计数质数 算法解析
☆打卡算法☆LeetCode 204. 计数质数 算法解析