介绍
素数是指除了1和本身以外，不能被其他正整数整除的数。判断一个数是否为素数，在计算机编程中非常常见。Python作为一门高级编程语言，也可以用来进行素数的判断。
判断素数的方法
试除法
试除法是最简单的一种方法，即判断一个数 n 是否为素数，只需在 2 到 n-1 的范围内判断 n 是否被整除。
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True质数倍数法
质数倍数法是一种非常有效的方法，可以处理较大的素数。它的基本思想是从 2 开始，不断将它的倍数标记为合数，直到所需要的素数都被找到，这种方法可以大大减少试除数的个数。
def prime_sieve(n):
is_prime = [False] * 2 + [True] * (n - 1)
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i ** 2, n + 1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]小标题
生成素数序列
可以通过生成素数序列的方式，找到所有小于等于给定值的素数。下面是利用试除法生成素数序列的代码：
def primes_sieve(n):
is_prime = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i ** 2, n + 1, i):
is_prime[j] = False
return [i for i in range(2, n + 1) if is_prime[i]]这段代码利用一个布尔型列表 is_prime 记录每个数是否为素数。首先将 is_prime 中的每个元素置为 True，然后从 2 开始，在 range(2, int(n ** 0.5) + 1) 中循环，如果 is_prime[i] 为 True，那么将 i * 2、i * 3、i * 4 …… 等数全部标记为 False。
多重判断素数
为了判断一个大整数是否为素数，可以使用多重判断法，例如同余检验法、费马小定理等。其中，费马小定理的判断方式比较简单，可以用下面的代码实现：
def is_prime(n):
if n <= 1:
return False
elif n <= 3:
return True
elif n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True总结
判断素数是计算机编程中的基本技能之一，Python提供了多种计算方式，包括试除法、质数倍数法、费马小定理等。如果要处理大的素数，可以使用更加高效的多重判断素数的方法。无论使用哪种方法，都需要注意处理好边界情况，以保证程序的正确性。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/245104.html
微信扫一扫 
支付宝扫一扫 