美文网首页
力扣(LeetCode)之统计n以内的素数个数

力扣(LeetCode)之统计n以内的素数个数

作者: 小黄不头秃 | 来源:发表于2023-09-07 00:46 被阅读0次
题目:

统计n以内的素数个数

示例:

输入:100 
输出:25
方法1:暴力算法解决

这是最容易想到的方法,我们需要遍历从2到x之间的值,判断每一个值是否为素数。判断素数的方法也很简单,就是让该值n除以[2, n]的数,如果能整除,说明不是素数。其具体代码如下:

# 暴力搜索算法
def fun1(x):
    counter = 0 
    for i in range(2,x):
        counter += isPrime(i)
    return counter

# 判断是否为素数
def isPrime(i):
    for n in range(2, i):
        if i % n == 0:
            return 0 
    return 1 
方法2:埃氏筛选

埃筛法是基于暴力算法的一种改进算法,这里我们考虑到有些合数我们是没有必要计算是否为素数的。那怎么去排除呢?当我们知道了2是素数,那么2*2、3*2、4*2、5*2、6*2,这样,这些就都是合数,我们就能够排除很多的合数。在编码上,我们仅需要设置一个标志位数组,用来标记是否为素数或者合数。我们把对应位置上的标记置为True就好了。这便是埃筛法。其具体实现代码如下:并且可以小小的改进一下:

# 埃筛法初级版本
def fun2(x):
    flag =  [False]*x # False 为素数,True为合数 
    counter = 0
    for i in range(2, x):
        if flag[i] == False:
            counter+=1 
            j = 2*i 
            while j<x:
                flag[j] = True
                j += i
    return counter

# 埃筛法优化版本
def fun3(x):
    flag =  [False]*x # False 为素数,True为合数 
    counter = 0
    for i in range(2, x):
        if flag[i] == False:
            counter+=1 
            j = i*i # 仅需改变这里,降低时间复杂度
            while j<x:
                flag[j] = True
                j += i
    return counter

相关文章

网友评论

      本文标题:力扣(LeetCode)之统计n以内的素数个数

      本文链接:https://www.haomeiwen.com/subject/lbyzmdtx.html