正文

python中如何算出素数

小六 /46 浏览量
1226

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

方法一：试除法

试除法是一种简单直观的素数检测方法，通过遍历从2到给定数字的平方根之间的所有整数，检查目标数字是否能被这些数整除。如果能被整除，则该数不是素数；否则，它是素数。

 import math def is_prime（n）: if n <= 1: return False for i in range（2, int（math.sqrt（n）） + 1）: if n % i == 0: return False return True 示例：检查一个数是否为素数 n = int（input（"请输入一个整数："）） if is_prime（n）: print（f"{n} 是素数。"） else: print（f"{n} 不是素数。"）

方法二：筛选法（埃拉托斯特尼筛法）

筛选法是一种更高效的素数检测方法，通过逐步筛选掉合数来找到素数。

 def sieve_of_eratosthenes（limit）: is_prime = [True] * （limit + 1） is_prime = is_prime = False for i in range（2, int（math.sqrt（limit）） + 1）: if is_prime[i]: for j in range（i * i, limit + 1, i）: is_prime[j] = False return [i for i in range（limit + 1） if is_prime[i]] 示例：找出小于等于100的所有素数 primes = sieve_of_eratosthenes（100） print（primes）

以上两种方法都可以用来计算素数。试除法适用于较小的数字，而筛选法在处理较大数字时效率更高。

您可以根据需要选择合适的方法来计算素数

-- 展开阅读全文 --