目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
204-计数质数
访问量:2441
一、题目
地址:https://leetcode.com/problems/count-primes/
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
二、解法
分析:比较2~ n-1,之间的数是否为质数
如何判断一个数M是否为质数呢?如果M能够被小于M的数整除,那么M就不是质数。否则为质数。
1、解法1
思路:这种方式比较好理解,对于任何一个数M,只需要从2开始,一直到小于其自身,依次判断能否被M整除,能则不是质数,都不能整除则为质数。
func countPrimes(n int) int { var count int for i := n - 1; i >= 2; i -- { //判断i是否为质数 var isPrime bool = true for j := 2; j < i; j ++ { if i%j == 0 { //不是一个质数 isPrime = false break } } if isPrime { count++ } } return count }
2、解法2
思路:解法1中,针对每个数n都遍历n-1次,其实是很浪费的。我们知道,如果一个大于1的数M,不是质数,那么必然存在两个约数m1,m2, m1 * m2 = M。根据这个发现,我们判断M是否为质数,只需要判断m1,不需要判断m2。以此内推M的有很多对m1和m2,即(ma1, mb1),(ma2, mb2),(ma3, mb3)。。。。(man, mbn),假设man 不大于mbn,那么我们仅仅需要比较(ma1,ma2,ma3.....man)是否为质数即可。那么man是多少呢?我们知道man * mbn = M,man <= mbn,所以可以得出 man * man = M,进而求出man的最大值。所以,每次仅仅需要比较到 math.Sqrt(M)为止。
func countPrimes(n int) int { var count int for i := n - 1; i >= 2; i -- { //判断i是否为质数 var isPrime bool = true for j := 2; j <= int(math.Sqrt(float64(i))); j ++ { if i%j == 0 { //不是一个质数 isPrime = false break } } if isPrime { count++ } } return count }
三、补充
1、什么是质数
质数,又被称为素数。就是在所有比1大的整数中,除了1和它本身以外,不再有别的因数,这种整数叫做质数。
和质数相对应的是合数,指的是除了能被1和本身整除外,还能被其他数(0除外)整除的数。
备注:1既不是质数,也不是合数
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助