求解素数的三种方法
首先明白一下什么是素数，素数又名质数，除了2以外就是它本身只能拆分成1和自身相乘而的来的数，如7就是一个素数，他只能由1*7得到，而6不是一个素数，因为它既可以由1*6得到，也可以由2*3得到。
1.【朴素法】求解：
那么知道一个素数的概念，我们便有了一个最朴素的方法求解，即从2~n，每一个数i进行一个判断，这个数字i从2到i-1之间，是否存在一个数字可以与之求余=0的情况，如果没有，则这是一个素数。
primesNumber = []
def is_prime(n):
for i in range(2, n-1):
if n % i == 0:
return False
return True
def primes(number):
for i in range(2, number):
if is_prime(i):
primesNumber.append(i)
primes(10000)
print(primesNumber)
一个简单的优化就是，在筛选的时候将判断数据的上届使用sqrt开平方的方式简化判断数据，使用6这个数字就可以很好理解，sqrt(6)约等于2.4，取整后就是2，那么存在一个2*3=6可以满足，这与求完整的数据是一样的，只不过更加高效。
primesNumber = []
def is_prime(n):
for i in range(2, int(n ** 0.5)):
if n % i == 0:
return False
return True
def primes(number):
for i in range(2, number):
if is_prime(i):
primesNumber.append(i)
#30000的时候会遇到Python的List存储超限的问题，导致无法全部存入
primes(20000)
print(primesNumber)
- 朴素求法的时间复杂度是O(n^2)。
此外，朴素方法一些变种可以间接性的增加处理速度，但基本上都是保持在这个复杂度了。
这里要注意一个Python的问题，我们采取List进行存放素数，然而Python的List的空间限制原因，导致我们求到大概3*10^4大小的数字的同时会发生一些溢出现象，这个时候是没有报错的，可以有两个解决的思路，这里就不帮助解决了（不然偏题）
- List扩容，或者使用多段List（操作上没有那么方便）
- 不存储素数，将所需要的数据直接输出
2.埃氏筛法
埃式筛法的思想是：对于不超过 n 的每个非负整数 p，删除 2*p, 3*p, 4*p,…，当处理完所有数之后，还没有被删除的就是素数。
我们可以从2开始，从小到大扫描每个数x,把x的倍数x*2,x*3,…x*(N/x)标记为非质数【此处其实可以优化，不用从2倍开始，因为对于每个数x,x的2倍，3倍都会被2,3，..<x的数筛过，因此只需从x倍开始】。
当扫描到一个数x时，若未被标记为非质数，那么该数便是质数，因为它能在比它小的数的过筛过程中逃过，就说明它前面没有一个数是它的倍数，然一个数的因子只可能比它小，因此我们可以断定，该数x便是一个素数。
一个简单的理解就是：利用倍数规则，将2的倍数，3的倍数，4的倍数，5的倍数等数字依次从素数表中删除，本质上是寻找非素数，但是总数-非素数=素数。
具体的代码如下：
# 生成一个奇数序列
def _odd_iter():
n = 1
while True:
n = n + 2
yield n
# 筛选函数，保留不能整除的，筛掉可以整除的，即倍数。
def _not_divisible(n):
return lambda x: x % n > 0
# 求素数函数。
def primes():
yield 2
it = _odd_iter() # 初始序列
while True:
n = next(it)
yield n
it = filter(_not_divisible(n), it) # it在不断的next调用中，进行筛选。
# 输出100000以内的所有素数,速度稍微快一丢丢：
for n in primes():
if n < 100000:
print(n, end=' ')
else:
break
这份代码采取利用生成器——filter()筛选函数进行过滤，这样写比较直观而且filter过滤的速度相当快，但如果基础不是很好可以参考一下这个C语言版本的，较为容易理解。
bool isprime[10000005];
void aishiPrime(int n){
memset(isprime,true,sizeof(isprime));
isprime[1]=false;
for (int i=2; i*i<=n; i++){
if (isprime[i]) {
for(int j=i*i;j<=n; j+=i)
isprime[j]=false;
}
}
}- 埃氏筛法的时间复杂度为：O(n*logn)
3.欧拉筛（线性筛）
欧拉筛的思想是：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
合数：【摘自百度百科】合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。最小的合数是4。其中，完全数与相亲数是以它为基础的。
如：385这个数，385= 5 * 7* 11，会被5的倍数时标记一次，7的倍数时标记一次，11的倍数时标记一次，造成效率达不到最优。而线性筛法基于改进这个不足的基础上，在线性时间内，也就是O(n)，用筛选的方法把素数找出来。
(从网上盗来的图2333333)
代码如下为：
#欧拉筛选--线性筛
# 返回小于r的素数列表
def oula(r):
# 全部初始化为0
prime = [0 for i in range(r+1)]
# 存放素数
common = []
for i in range(2, r+1):
if prime[i] == 0:
common.append(i)
for j in common:
if i*j > r:
break
prime[i*j] = 1
#将重复筛选剔除
if i % j == 0:
break
return common
prime = oula(20000)
print(prime)
- 欧拉筛的时间复杂度为O(n)
从时间的运行上相对而言，素数的筛选，最理想的还是欧拉筛，但是需要在前文理解的基础上才能够很好的写出来。
0 条评论