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

题目：

统计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