共计 778 个字符,预计需要花费 2 分钟才能阅读完成。
判断一个数是否为素数的方法有以下几种:
- 暴力法:对于每个大于 1 且小于该数的整数,判断该整数能否整除该数。如果存在能整除的整数,则该数不是素数;否则,该数是素数。这种方法的时间复杂度是 O(n)。
def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
- 优化暴力法:在判断能否整除时,可以只判断小于等于√n 的整数。因为如果存在大于√n 的整数能整除 n,那么一定存在小于√n 的整数能整除 n。这种方法的时间复杂度是 O(√n)。
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
- Sieve of Eratosthenes(埃拉托斯特尼筛法):先假设所有数都是素数,然后从 2 开始,将所有 2 的倍数标记为合数,再从 3 开始,将所有 3 的倍数标记为合数,以此类推,直到√n。标记完成后,剩下未被标记的数即为素数。这种方法的时间复杂度是 O(nloglogn)。
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
if is_prime[p]:
for i in range(p * p, n + 1, p):
is_prime[i] = False
p += 1
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
return primes
以上是一些常用的判断素数的方法,不同方法的效率不同,可以根据具体需求选择合适的方法。
丸趣 TV 网 – 提供最优质的资源集合!
正文完