python求质数各种方法_求质数的算法

激活谷笔记 • 2025-05-13 13:51 • 阅读 113

在Python中，求质数可以通过多种方法实现，以下是几种常见的方法：

方法一：穷举法

 def countPrimes1（n）: if n <= 2: return 0 res = [] for i in range（2, n）: flag = 0 for j in range（2, i）: if i % j == 0: flag = 1 break if flag == 0: res.append（i） return len（res）

方法二：利用定理优化

 import math def is_prime（num）: if num < 2: return False for i in range（2, int（math.sqrt（num）） + 1）: if num % i == 0: return False return True def get_primes（n）: primes = [] for i in range（2, n）: if is_prime（i）: primes.append（i） return primes

方法三：埃拉托斯特尼筛法

 def sieve_of_eratosthenes（n）: sieve = [True] * （n + 1） sieve = sieve = False for i in range（2, int（math.sqrt（n）） + 1）: if sieve[i]: for j in range（i * i, n + 1, i）: sieve[j] = False return [i for i in range（2, n + 1） if sieve[i]]

方法四：使用生成器

 def prime_generator（n）: for num in range（2, n + 1）: if all（num % i for i in range（2, int（math.sqrt（num）） + 1））: yield num

方法五：使用filter函数

 def func_get_prime（n）: return filter（lambda x: not any（x % i == 0 for i in range（2, int（math.sqrt（x）） + 1））, range（2, n + 1））

以上方法均可用来找出指定范围内的所有质数。你可以根据具体需求选择合适的方法。需要注意的是，随着n的增大，计算质数所需的时间和资源也会增加，因此对于较大的n值，可能需要考虑更高效的算法

python求质数各种方法_求质数的算法

相关推荐