这年头，谁还不会点 Python 啊？但是，真要让你手撸一个找素数的函数，你确定你能写得又快又漂亮？别慌，咱今天就好好聊聊这事儿，用 Python 怎么把素数给揪出来。
最简单的，也是最容易想到的，就是直接暴力试除法。啥叫暴力？就是从 2 开始，一直除到这个数的平方根（取整），看看能不能被整除。如果都不能，那它就是素数！
“`python
import math
def is_prime_brute_force(number):
“””
判断一个数是否为素数（暴力试除法）
“””
if number <= 1:
return False
for i in range(2, int(math.sqrt(number)) + 1):
if number % i == 0:
return False
return True
举个例子
print(is_prime_brute_force(17)) # True
print(is_prime_brute_force(20)) # False
“`
这段代码够直白吧？但是，说实话，效率真不高！尤其当你需要找一大堆素数的时候，那速度简直让人崩溃。想想，如果让你判断1000007是不是素数，它得试除到1000多，想想都觉得慢。
那有没有快一点的方法呢？当然有！
接下来要说的，是埃拉托斯特尼筛法。这个方法听起来高大上，其实原理很简单：
- 先把 2 到 n 的所有整数都列出来。
- 找到最小的素数 2，然后把 2 的所有倍数都划掉（因为它们肯定不是素数）。
- 找到下一个没有被划掉的数，它一定是素数。然后把它的所有倍数都划掉。
- 重复步骤 3，直到所有小于等于 n 的数的倍数都被划掉。
剩下的那些没被划掉的，就是素数啦！
这就像筛沙子一样，把不是素数的“沙子”都筛掉，剩下的就是金灿灿的“素数”了。
“`python
def eratosthenes_sieve(n):
“””
埃拉托斯特尼筛法求n以内的所有素数
“””
prime = [True] * (n + 1) # 创建一个布尔数组，初始都设为True
prime[0] = prime[1] = False # 0和1不是素数
p = 2
while (p * p <= n):
if (prime[p] == True):
# 如果p是素数，则将其倍数都标记为非素数
for i in range(p * p, n + 1, p):
prime[i] = False
p += 1
# 收集所有素数
primes = []
for p in range(2, n + 1):
if prime[p]:
primes.append(p)
return primes
试试看
primes = eratosthenes_sieve(50)
print(primes) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
“`
这段代码效率比暴力试除法高多了！特别是当 n 很大的时候，优势更明显。但是，它也有缺点：需要占用额外的空间来存储那个布尔数组。
如果你对空间复杂度比较敏感，或者 n 非常非常大，甚至超出了内存的限制，那该怎么办呢？那就需要用到一些更高级的算法了，比如线性筛（欧拉筛）。
线性筛的原理稍微复杂一点，但它的核心思想是：每个合数只会被它的最小质因子筛掉一次。这样，就可以保证每个数只会被处理一次，从而达到线性时间复杂度。
“`python
def linear_sieve(n):
“””
线性筛（欧拉筛）求n以内的所有素数
“””
primes = []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(len(primes)):
if i * primes[j] > n:
break
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
break
return primes
再试试看
primes = linear_sieve(50)
print(primes) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
“`
这段代码，虽然看起来比埃拉托斯特尼筛法复杂一些，但它的效率更高，空间复杂度也更优秀。这绝对是 Python 求素数的利器！
所以说，Python 求素数，方法真的很多。用哪种方法，取决于你的具体需求。如果只是判断一个数是不是素数，暴力试除法也够用。如果需要找一大堆素数，那就得考虑埃拉托斯特尼筛法或者线性筛了。记住，没有最好的算法，只有最合适的算法。
写代码嘛，就像谈恋爱，适合自己的才是最好的。
当然，除了上面这些，还有一些更高级的素数判定算法，比如 Miller-Rabin 素性测试。但那些算法比较复杂，一般情况下用不到。所以，掌握了上面这几种方法，就足够应付大部分场景了。
最后，再啰嗦一句：写代码，多思考，多实践，才能真正掌握！别光看不练，赶紧动手试试吧！说不定，你还能发现更牛的素数算法呢！
评论(0)