[教程]揭秘Python中表示质数的巧妙方法，轻松掌握编程技巧！

引言质数，作为数学中一个重要的概念，在编程领域也有着广泛的应用。在Python中，表示质数的方法有很多种，本文将介绍几种常见的方法，帮助读者轻松掌握编程技巧。一、基本概念在Python中，质数是指只能...

引言

质数，作为数学中一个重要的概念，在编程领域也有着广泛的应用。在Python中，表示质数的方法有很多种，本文将介绍几种常见的方法，帮助读者轻松掌握编程技巧。

一、基本概念

在Python中，质数是指只能被1和自身整除的大于1的自然数。例如：2、3、5、7等都是质数。

二、穷举法

穷举法是最简单的一种判断质数的方法。它通过循环遍历一个数的所有可能的因数，判断是否存在能够整除该数的因数。如果不存在，则该数为质数。

代码示例

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True
# 测试
num = 29
if is_prime(num): print(f"{num} 是质数")
else: print(f"{num} 不是质数")

三、埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种高效的找出一定范围内所有质数的方法。该方法通过不断排除合数来找到质数。

代码示例

def sieve_of_eratosthenes(limit): prime = [True] * (limit + 1) p = 2 while p * p <= limit: if prime[p]: for i in range(p * p, limit + 1, p): prime[i] = False p += 1 primes = [p for p in range(2, limit + 1) if prime[p]] return primes
# 测试
limit = 100
primes = sieve_of_eratosthenes(limit)
print(f"小于等于{limit}的质数有：{primes}")

四、Miller-Rabin素数测试

Miller-Rabin素数测试是一种概率性的质数测试方法，对于大数质数的判断非常有效。

代码示例

import random
def miller_rabin(n, k=5): if n == 2 or n == 3: return True if n <= 1 or n % 2 == 0: return False # 写成d*2^r+1的形式 r, d = 0, n - 1 while d % 2 == 0: r += 1 d //= 2 # 进行k次测试 for _ in range(k): a = random.randint(2, n - 2) x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True
# 测试
num = 101
if miller_rabin(num): print(f"{num} 是质数")
else: print(f"{num} 不是质数")

五、总结

本文介绍了Python中表示质数的几种方法，包括穷举法、埃拉托斯特尼筛法和Miller-Rabin素数测试。通过学习这些方法，读者可以轻松掌握编程技巧，并在实际应用中灵活运用。