素数，又称质数，是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。在计算机编程中，判断一个数是否为素数一直是一个经典的问题，本文将介绍如何使用Python实现100以内素数的判断。
一、素数的判断方法
判断一个数是否为素数有多种方法，以下介绍其中两种。
1.试除法
首先我们可以通过试除法来判断一个数是否为素数。假设要判断的数为n，首先从2开始，一直到n-1逐个尝试除以n，如果都除不尽，那么n就是素数，反之则不是。
def is_prime(n):
for i in range(2,n):
if n%i == 0:
return False
return True
使用上述代码即可判断一个数是否为素数。需要注意的是，这个算法的时间复杂度为O(n)，并不是最优的算法。
2. Eratosthenes筛法
Eratosthenes筛法是一种用来求一定范围内所有素数的算法。算法的流程如下：
1.用2~n之间的所有数初始化一个表，将表中所有的数标记为1。
2.从2开始，将表中所有2的倍数标记为0。
3.从3开始，如果这个数还没有被标记为0，那么将表中所有它的倍数标记为0。
4.重复第3步，直到处理完n为止。
最终所有值为1的下标即为素数。
def eratosthenes(n):
primes = [1]*n
primes[0],primes[1] = 0,0
for i in range(2,int(n**0.5)+1):
if primes[i]:
for j in range(i**2,n,i):
primes[j] = 0
return [x for x in range(n) if primes[x]]
使用上述代码即可返回100以内的所有素数，由于算法的时间复杂度为O(n log log n)，因此在计算大量素数的情况下，效率更高。
二、完整代码
def is_prime(n):
for i in range(2,n):
if n%i == 0:
return False
return True
def eratosthenes(n):
primes = [True]*n
primes[0],primes[1] = False,False
for i in range(2,int(n**0.5)+1):
if primes[i]:
for j in range(i**2,n,i):
primes[j] = False
return [x for x in range(n) if primes[x]]
print("试除法：", [x for x in range(2,101) if is_prime(x)])
print("Eratosthenes筛法：", eratosthenes(100))
以上为完整的Python代码，可以直接复制粘贴到IDE或者Jupyter Notebook中运行。
三、总结
通过本文我们了解了两种算法去判断素数，试除法和Eratosthenes筛法，其中Eratosthenes筛法时间复杂度更低。若需要判断大量素数时，建议使用Eratosthenes筛法来实现。
原创文章，作者：ACKVU，如若转载，请注明出处：https://www.506064.com/n/374687.html
微信扫一扫 
支付宝扫一扫 