当前位置：首页 > web >正文

Python中质数筛选及优化效率对比

web 2025/7/21 20:43:30

题记：

最近自学Python，出于好奇，想从1~100000000共1亿个数中找出所有质数个数，用欧拉筛和埃氏筛两种方法筛选质数，让大家看看在Python中原生方法与使用第三方库的效率对比，这差异是不是也太大了点？另外在Python中，欧拉筛怎么还比不过埃氏筛？在C++中可不是这样啊？！

测试源代码：

import numpy as np
from numba import njit
import timen=100_000_000  #测试1亿个数def euler_sieve(n):"""使用欧拉筛法找出小于等于n的所有质数(原生方法)"""if n < 2:return []is_prime = [True] * (n + 1)  # 初始化素数标记数组primes = []                  # 存储所有质数for i in range(2, n + 1):if is_prime[i]:primes.append(i)for p in primes:   # 遍历当前已找到的质数，筛除 i * pm = i *pif m > n:breakis_prime[m] = Falseif i % p == 0:break  # 确保每个合数只被其最小质因子筛一次return primes@njit #利用@njit 提升性能!
def euler_sieve_njit(n):"""直接操作NumPy数组，Numba@njit优化的欧拉筛法"""if n < 2:return np.zeros(0, dtype=np.int64)is_prime = np.ones(n + 1, dtype=np.bool_)is_prime[0] = is_prime[1] = Falseprimes = np.zeros(n, dtype=np.int64)  # 预分配足够大的数组count = 0for i in range(2, n + 1):if is_prime[i]:primes[count] = icount += 1j = 0while j < count:p = primes[j]m = i * pif m > n:breakis_prime[m] = Falseif i % p == 0:breakj += 1return primes[:count]  # 只返回有效部分def sieve_eratosthenes(n):"""使用埃拉托斯特尼筛法找出小于等于n的所有质数(原生方法)"""if n < 2:return []is_prime = [True] * (n + 1)is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数for i in range(2, int(n ** 0.5) + 1):if is_prime[i]:
#             将 i 的所有倍数标记为非质数（切片赋值内存溢出使用）
#             for j in range(i * i, n + 1, i):
#                 is_prime[j] = False                # 利用切片赋值比循环效率更高！但数值太大(超过1亿)会内存溢出错误is_prime[i*i::i] = [False] * ((n - i*i) // i + 1)# 收集所有质数primes = [i for i, prime in enumerate(is_prime) if prime]return primesdef sieve_eratosthenes_numpy(n):"""NumPy优化的埃拉托斯特尼筛法"""if n < 2:return np.zeros(0, dtype=np.int64)  # 返回空数组is_prime = np.ones(n + 1, dtype=np.bool_)is_prime[0:2] = False  # 0和1不是质数for i in range(2, int(np.sqrt(n)) + 1):if is_prime[i]:is_prime[i*i::i] = False  # 标记所有i的倍数,NumPy会自动广播return np.nonzero(is_prime)[0]  # 两者功能一类似
#     return np.where(is_prime)[0]   # 获取所有为 True 的索引"""==============测试============="""
start = time.time()
primes = euler_sieve(n)
end = time.time()
print(f"欧拉筛法 | 耗时: {end - start:.2f}s | 质数数量: {len(primes)}")start = time.time()
primes = euler_sieve_njit(n)
end = time.time()
print(f"欧拉筛法-优化 | 耗时: {end - start:.2f}s | 质数数量: {len(primes)}")start = time.time()
primes = sieve_eratosthenes(n)
end = time.time()
print(f"埃氏筛法 | 耗时: {end - start:.2f}s | 质数数量: {len(primes)}")start = time.time()
primes = sieve_eratosthenes_numpy(n)
end = time.time()
print(f"埃氏筛法-优化 | 耗时: {end - start:.2f}s | 质数数量: {len(primes)}")

输出结果：