正文

python如何找出所有的素数

小六 /24 浏览量
0305

在Python中，求所有素数可以通过多种方法实现，以下是两种常见的方法：

方法一：筛选法（Sieve of Eratosthenes）

筛选法是一种高效的算法，用于找出一定范围内所有的素数。

 def get_primes（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]] print（get_primes（100））

方法二：穷举法

穷举法是最直接的方法，通过遍历每个数来判断它是否为素数。

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

以上两种方法都可以用来找出指定范围内的所有素数。筛选法的时间复杂度较低，适用于较大的数值范围；而穷举法简单直观，但时间复杂度较高，适用于较小的数值范围。

-- 展开阅读全文 --