筛法求素数
本文将介绍 埃拉托斯特尼筛法 和 欧拉线性筛法 的基本原理,并以此思路实现这两种求素数的算法。
筛法求素数
埃拉托斯特尼筛法
基本思路
当一个数是素数的时候,它的倍数肯定不是素数,对于这些数可以直接标记筛除。
时间复杂度
\(O(nloglogn)\)
算法实现
java
1 | public class SimpleSieve { |
python
1 | from typing import List |
欧拉线性筛法
基本思路
任意一个合数(2 不是合数),都可以表示成素数的乘积。
每个合数必有一个最小素因子,如果每个合数都用最小素因子筛去,那个这个合数就不会被重复标记筛去,所以算法为线性时间复杂度。
例如合数 30 = 2 * 3 * 5
,这个合数一定是被最小素因子 2 筛去的。
时间复杂度
\(O(n)\)
算法实现
java
1 | import java.util.ArrayList; |
python
1 | from typing import List |
References
-
2019-05-24
二分查找也称 折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
-
2020-05-02
一些经典的二叉树练习题,帮助理解掌握二叉树的各种遍历方法和递归地解决问题的思路。
-
2020-04-25
了解树和二叉树的相关概念;
理解不同遍历方法的工作原理,掌握相应遍历方法的递归和迭代实现;
- 前序遍历
- 中序遍历
- 后序遍历
- 层次遍历
-
2019-06-03
这篇文章主要总结了面试中需要掌握的几个方面,包括数据结构、算法和数据操作、高质量的代码、解决面试题的思路、优化时间和空间效率以及面试中的各项能力。在数据结构方面,需要掌握常见的数据结构,如数组、链表、栈、队列、树、图等,并能够熟练地进行操作。在算法和数据操作方面,需要掌握常见的算法,如排序、查找、递归、动态规划等,并能够熟练地运用到实际问题中。在高质量的代码方面,需要注意代码的可读性、可维护性和可扩展性,并且要遵循一定的编码规范。在解决面试题的思路方面,需要掌握常见的解题思路,如暴力枚举、贪心算法、分治算法等,并能够灵活运用到实际问题中。在优化时间和空间效率方面,需要注意算法的时间复杂度和空间复杂度,并能够对算法进行优化。在面试中的各项能力方面,需要注意沟通能力、团队合作能力、问题解决能力等。
-
2020-03-29
Python 列表具有内置的 list.sort() 方法,该方法可就地修改列表。还有一个 sorted() 内置函数,可从迭代器构建新的排序列表。
因为 Python3 中 sorted() 和 list.sort() 放弃了类似 C++ 中的 cmp 写法,本文将展示官方推荐替代解决方案,以实现自定义的两个参数的比较函数,并详细分析了 cmp_to_key 函数实现原理。