本文主要是介绍线性筛法求素数(欧拉筛法)(求质数,O(n)时间复杂度)(外加求每个整数的最小质因子)(python),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言:
python 中求质数的方法有好几种,这里就讲解时间复杂度最低的算法欧拉筛法,时间复杂度为O(n),这是数论中也是算法比赛中必须掌握的方法。
本篇博客还会额外讲解求每个整数的最小质因子,什么是质因子?顾名思义,就是是质数的因子,求这个有什么用呢?下篇博客X的因子链(数论,python)(算术基本定理)(欧拉筛法)会给大家讲解一道例题,在例题中讲解它的用法。
思路:
线性筛法的整体思路是(代码里有详细注释):
- 初始化一个长度为 n 的数组,再定义一个长度为n的bool类型数组,用来表示每个数是否为素数,为True表示不是素数
- 从2遍历到n,判断是否为素数(bool类型是否为False),若是素数,则将它的倍数标记为True
代码如下:
N = 10000
prime = [0] * N # 存储所有的质数
cnt = 0 # 质数的个数
vis = [False] * N # 标记数是否被筛过
for i in range(2, N):if not vis[i]:prime[cnt] = i # 将当前数 i 记录为质数cnt += 1for j in range(cnt):if prime[j] * i >= N: # 如果超出n 则无需后续操作直接退出循环breakvis[prime[j] * i] = True # 标记 i*prime[j] 已经被筛过# 如果i是前面某个素数的倍数时, 说明i以后会由某个更大的数乘这个小素数筛去同理,# 之后的筛数也是没有必要的, 因此在这个时候, 就可以跳出循环了if i % prime[j] == 0:break
欧拉算法的特点就是每个数只会被自己的最小质因数筛过一次,所以由此保证了线性的时间复杂度。
求最小质因子只需在求素数的基础上加上两行代码即可
首先分析质数和非质数的最小质因子是什么。
- 质数的最小质因子是它本身(因为1是因子但不是质数)
- 非质数的最小质因子是什么呢?按正常思路分析不好得出结论,但在求素数的过程中有一步是对质数的倍数进行标记,通过这一步就可以判断出非质数的最小质因子是什么了。
代码如下:
N = 10000
prime = [0] * N # 存储所有的质数
cnt = 0 # 质数的个数
vis = [False] * N # 标记数是否被筛过
st = [0] * N # 存储数的最小质因数for i in range(2, N):if not vis[i]:prime[cnt] = i # 将当前数 i 记录为质数st[i] = i # 当前数 i 的最小质因数为自身cnt += 1for j in range(cnt):if prime[j] * i >= N: # 如果超出n 则无需后续操作直接退出循环breakst[prime[j] * i] = prime[j] # 将 i*prime[j] 的最小质因数标记为 prime[j]vis[prime[j] * i] = True # 标记 i*prime[j] 已经被筛过# 如果i是前面某个素数的倍数时, 说明i以后会由某个更大的数乘这个小素数筛去同理,# 之后的筛数也是没有必要的, 因此在这个时候, 就可以跳出循环了if i % prime[j] == 0:break
总结:
欧拉筛法是很多数论题型解法的“敲门砖”,下篇博客X的因子链(数论,python)(算术基本定理)(欧拉筛法)将讲解一道比较难的数论题,该题用到了本篇博客的欧拉筛法和最小质因子求法。
这篇关于线性筛法求素数(欧拉筛法)(求质数,O(n)时间复杂度)(外加求每个整数的最小质因子)(python)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!