python求素数,试除法

这是运用埃拉托斯特尼筛法找到的50以内的素数列表：

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$$

如果您需求核算其他规模内的素数，请告诉我具体的规模。

Python求素数办法详解

素数，又称质数，是数学中一个非常重要的概念。它指的是一个大于1的自然数，除了1和它自身以外，不能被其他自然数整除的数。在核算机科学、密码学等范畴，素数都有着广泛的运用。本文将具体介绍Python中求素数的办法，包含根本办法和优化办法。

根本办法：试除法

什么是试除法

试除法是一种最简略的求素数的办法。它的根本思想是：关于给定的一个数n，从2开端，顺次测验将n除以2、3、4、5……直到n的平方根。如果在测验的进程中，n能被某个数整除，那么n就不是素数；不然，n是素数。

Python完成

下面是一个运用试除法判别素数的Python函数：

```python

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

示例

```python

print(is_prime(2)) 输出：True

print(is_prime(4)) 输出：False

print(is_prime(17)) 输出：True

优化办法：埃拉托斯特尼筛法

什么是埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更高效的求素数办法。它的根本思想是：从2开端，将2的倍数（除了2自身）悉数筛掉；然后找到下一个未被筛掉的数，它便是下一个素数；接着将这个素数的倍数（除了它自身）悉数筛掉；重复这个进程，直到到达所需的素数规模。

Python完成

下面是一个运用埃拉托斯特尼筛法求100以内一切素数的Python函数：

```python

def sieve_of_eratosthenes(limit):

is_prime = [True] (limit 1)

is_prime[0] = is_prime[1] = False

for i in range(2, int(limit0.5) 1):

if is_prime[i]:

for j in range(ii, limit 1, i):

is_prime[j] = False

primes = [i for i, prime in enumerate(is_prime) if prime]

return primes

print(sieve_of_eratosthenes(100))

示例

```python

输出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

本文介绍了Python中求素数的两种办法：试除法和埃拉托斯特尼筛法。试除法简略易懂，但功率较低；埃拉托斯特尼筛法功率较高，但需求更多的内存空间。在实践运用中，能够依据需求挑选适宜的办法。

扩展阅览

- [Python中的数学函数](https://docs.python.org/3/library/math.html)

- [Python中的列表推导式](https://docs.python.org/3/tutorial/datastructures.htmllist-comprehensions)

- [Python中的生成器表达式](https://docs.python.org/3/tutorial/datastructures.htmlgenerator-expressions)