python如何确定素数
原创Python中确定素数的几种方法
在Python中,确定一个数是否为素数有多种方法,以下是一些常见的方法:
1. 使用标准库math模块
Python的math模块提供了一个函数isqrt
,可以用来确定一个数是否为素数。
import math def is_prime(n): if n <= 1: return False if n <= 3: return True if 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
2. 使用试除法
试除法是一种简单的确定素数的方法,它通过不断试除2到n的平方根之间的所有整数,看它们是否能够整除n。
def is_prime(n): if n <= 1: return False for i in range(2, int(n0.5) + 1): if n % i == 0: return False return True
3. 使用埃拉托斯特尼筛法
埃拉托斯特尼筛法是一种高效的确定素数的方法,它通过筛选掉合数,留下素数。
def is_prime(n): if n <= 1: return False is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n0.5) + 1): if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False return is_prime[n]
上一篇:Python如何输出大数 下一篇:python如何调整表格