python用埃拉托斯特尼筛法编写判断素数的程序
时间: 2024-06-15 14:08:53 浏览: 16
埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种用于判断素数的经典算法。下面是使用Python编写的埃拉托斯特尼筛法判断素数的程序:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记数字是否为素数
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# 从2开始遍历到根号n
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# 将i的倍数标记为非素数
for j in range(i * i, n + 1, i):
is_prime[j] = False
# 收集所有素数
primes = [i for i in range(n + 1) if is_prime[i]]
return primes
# 示例:判断100以内的素数
primes = sieve_of_eratosthenes(100)
print(primes)
```
这段代码使用了一个布尔数组 `is_prime` 来标记数字是否为素数。首先将数组中的所有元素初始化为 `True`,然后从2开始遍历到根号n,如果当前数字是素数,则将其倍数标记为非素数。最后,收集所有标记为素数的数字,即为所求的素数列表。
相关问题
埃拉托斯特尼筛法判断素数的程序python
埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种用于判断素数的经典算法。下面是一个使用Python实现的埃拉托斯特尼筛法的程序:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记数字是否为素数
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
# 从2开始遍历到根号n
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# 将i的倍数标记为非素数
for j in range(i*i, n+1, i):
is_prime[j] = False
# 收集所有素数
primes = [i for i in range(n+1) if is_prime[i]]
return primes
# 示例:打印出100以内的所有素数
primes = sieve_of_eratosthenes(100)
print(primes)
```
这个程序首先创建了一个长度为n+1的布尔数组is_prime,用于标记数字是否为素数。然后从2开始遍历到根号n,如果当前数字i是素数,则将其倍数标记为非素数。最后,收集所有标记为素数的数字,即为所求的素数列表。
判断一个数是否为素数python埃拉托斯特尼筛法的优势
埃拉托斯特尼筛法是一种用于判断一个数是否为素数的高效算法。相较于其他判断素数的方法,它的优势在于可以提前筛选出一定范围内的所有素数,从而减少了判断的次数。在使用埃拉托斯特尼筛法时,我们可以先将从2开始的所有整数进行标记,然后从2开始依次遍历,将遍历到的素数的倍数进行标记,最终剩下的未被标记的数即为素数。这样一来,我们只需要遍历到输入数的平方根即可。