素数算法（普通求解，埃氏筛，欧拉筛）

本文主要是介绍素数算法（普通求解，埃氏筛，欧拉筛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

素数算法（常规求解，埃氏筛，欧拉筛）

1. 常规求解
- 1.1 原理解释
- 1.2 算法实现
2 . 埃氏筛
- 2.1 原理解释
- 2.2 算法实现
3. 欧拉筛
- 3.1 原理解释
- 3.2 算法实现

1. 常规求解

1.1 原理解释

枚举法是一种简单的求解素数的方法，其基本思想是从2开始逐个判断每个数字是否为素数。具体来说，对于一个待判断的数n，我们可以从2开始依次尝试将n除以小于等于n的开方的所有数，如果存在一个因子能够整除n，则n不是素数；否则n是素数。

这种方法的效率较低，特别是在处理大范围内的素数时，会耗费大量时间和计算资源。因此，在实际应用中，通常使用更加高效的质数筛选法或素性测试算法来求解素数。

1.2 算法实现

import mathdef is_prime(n):if n < 2:return Falsefor i in range(2, int(math.sqrt(n)) + 1):if n % i == 0:return Falsereturn True

其中，函数is_prime接受一个正整数n作为输入，返回一个布尔值，表示n是否为素数。在函数中，我们首先判断如果n小于2，则返回False，因为2是最小的素数。然后，我们从2开始循环，到n的开方的整数部分+1为止，依次判断是否存在能整除n的因数。如果找到一个可以整除n的数，则n不是素数，返回False；如果遍历完所有可能的因数，都没有找到可以整除n的数，则n是素数，返回True。

需要注意的是，枚举法只适用于判断较小的数字是否为素数。在实际应用中，通常需要判断的数字范围非常大，因此使用更加高效的算法求解素数是必要的。

2 . 埃氏筛

2.1 原理解释

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种常用的质数筛选法，可以高效地找出一定范围内的所有素数。其基本原理是通过逐步排除非素数的方式来筛选出素数。

具体步骤如下：

创建一个长度为n+1的布尔数组is_prime，初始化所有元素为True。is_prime[i]表示数字i是否为素数。

从2开始，遍历到√n，对于每个遇到的素数p，执行以下操作：

如果is_prime[p]为True，说明p是素数，将is_prime[p]置为False。
对于p的所有倍数i（i从2开始），将is_prime[i*p]置为False。这些数都不是素数，因为它们至少有一个因子p。
遍历完成后，所有is_prime[i]为True的索引i对应的数字i都是素数。

埃氏筛利用了一个重要的性质：如果一个数是素数，那么它的所有倍数都不是素数。因此，通过遍历素数的倍数并将其标记为非素数，我们可以排除一大批非素数，从而筛选出素数。

2.2 算法实现

import mathdef sieve_of_eratosthenes(n):is_prime = [True] * (n + 1)is_prime[0] = is_prime[1] = Falsefor p in range(2, int(math.sqrt(n)) + 1):if is_prime[p]:for i in range(p * p, n + 1, p):is_prime[i] = Falseprimes = [i for i in range(n + 1) if is_prime[i]]return primes

在代码中，我们首先创建了一个长度为n+1的布尔数组is_prime，并将所有元素初始化为True。然后，从2开始遍历到√n，对于每个素数p，将其倍数标记为非素数。遍历完成后，根据is_prime数组中值为True的索引，构建出素数列表primes并返回。

埃氏筛的时间复杂度为 O(n log log n)，其中n是待筛选的范围。该方法的优势在于其简单性和较低的时间复杂度，但当处理极大范围内的素数时，还有更优秀的算法可以使用，如线性筛（欧拉筛）法。

3. 欧拉筛

3.1 原理解释

欧拉筛（Euler’s sieve）是一种高效的质数筛选算法，通过遍历每个数并标记其最小质因数来筛选出所有素数。与埃氏筛不同，欧拉筛只标记每个数一次，因此其时间复杂度为 O(n)。

具体步骤如下：

创建一个长度为n+1的数组is_prime，初始化所有元素为True。is_prime[i]表示数字i是否为素数。

遍历2到n的每个数i，执行以下操作：

如果is_prime[i]为True，说明i为素数，将i加入素数列表primes。
遍历素数列表primes中的每个素数p，如果i * p <= n，将is_prime[i * p]置为False。
如果i能整除p，跳出内层循环，避免重复标记。
在欧拉筛中，我们利用了一个重要性质：每个合数都有一个最小质因数，而这个最小质因数不会大于它的平方根。因此，在遍历过程中，我们只需要标记每个数的最小质因数即可，无需遍历它的倍数。

3.2 算法实现

def euler_sieve(n):is_prime = [True] * (n + 1)primes = []for i in range(2, n + 1):if is_prime[i]:primes.append(i)for p in primes:if i * p > n:breakis_prime[i * p] = Falseif i % p == 0:breakreturn primes