iTesting软件测试知识分享

求1000以内的素数

算法问题逐渐成为面试题里的必考题目,但大多测试人员都对其不太重视,笔者也是如此,故决定开一个系列,不定期分享一些算法题目。今天来看一道经典的面试题,求1000内的素数。

素数定义:

除了1和它本身之外再不能被其他数整除的自然数。

##算法思想:

第一种解法 – 直接根据素数定义来,对于给定的数n,拿1~n-1的数去除n,只有n不能被任一个数整除,n才是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def prime(n):
for i in range(2, n): #1不是素数,所以循环从2开始
if n%i ==0:
return False
return True
def get_prime(x):
r_list = []
for n in range(2, x+1): #1不是素数,所以循环从2开始, 求到x为止的素食,所以循环需要到x+1.
if prime(n):
r_list.append(n)
return r_list
print((get_prime(1000))

看起来很简单对不对,但随着x的增大,时间复杂度开销太大了,有没有更好的方法呢?

  1. 对于一个自然数N,只要能被一个非1非自身的数整除,它就肯定不是素数。 我们一定要一个个的除过去吗?非也
  2. 对于一个自然数N,如果它不是素数,是合数,那么肯定存在1到N的两个数,n1×n2=N。 那么n1 和n2不可能两个都大于根号n(√N),不难理解吧?我们可以把n1和n2看
    成一对,假设n1 < √N,那么,只要n1能被N整除,N就不是素数。 也就是说, 只要2到√N之间的数能被N整除,那么N就不是素数,否则,N就是素数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def prime(n):
    for i in range(2, int(math.sqrt(n)+1)):
    if n%i ==0:
    return False
    return True
    def get_prime(x):
    r_list = []
    for n in range(2, x+1):
    if prime(n):
    r_list.append(n)
    return r_list
    print(len(get_prime(1000)))

对于每一个n, 查找范围是不是少了一半? 我们再来想下。

除2之外的偶数,会不会是素数?不可能把,也就是说,偶数只有2是素数,那么素数之剩下奇数了,优化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def prime(n):
for i in range(2, int(math.sqrt(n)+1)):
if n%i ==0:
return False
return True
def get_prime(x):
if x<2:
return None
if x ==2:
return 2
r_list = [2]
for n in range(3, x+1, 2):
if prime(n):
r_list.append(n)
return r_list
print(len(get_prime(1000)))

第二种解法 – 埃氏筛法.

  1. 列出从2开始的所有自然数,构造一个序列:2, 3, 4, 5, 6, 7, 8, 9, 10 …
  2. 取序列的第一个数2,它一定是素数,然后把序列的2的倍数筛掉, 剩下:3,5,7,9….
  3. 取新序列的第一个数3,它一定是素数,然后用3把序列的3的倍数筛掉:5,7,….
  4. 取新序列的第一个数5,然后用5把序列的5的倍数筛掉:7…
  5. 不断筛下去,就可以得到所有的素数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #以下代码摘抄自网络
    def _odd_iter():
    n = 1
    while True:
    n = n + 2
    yield n
    def _not_divisible(n): #先别着急理解这个函数,看后面。
    return lambda x: x % n > 0 #此处>0可以更改为!=0.不影响结果,原因是要把所有可以被素数整除的数筛选掉。
    def primes():
    yield 2
    it = _odd_iter() # 初始序列
    while True:
    n = next(it) # 返回序列的第一个数
    yield n
    it = filter(_not_divisible(n), it) # 构造新序列
    #难点在于理解这个_not_divisible函数里的x。filter函数用法是:filter(fuction,list):将list中每一个元素带入到function中,计算返回值,将返回值为True的list中的元素形成一个新的list。
    for n in primes():
    if n < 10:
    print(n)
    else:
    break
🐶 您的支持将鼓励我继续创作 🐶
-------------评论, 吐槽, 学习交流,请关注微信公众号 iTesting-------------
iTesting wechat
扫码关注,跟作者互动