题目:
统计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
网友评论