pathon埃拉托色尼筛
时间: 2024-10-12 13:13:12 浏览: 58
Python中的埃拉托斯特尼筛(Sieve of Eratosthenes)是一种经典算法,用于寻找一定范围内的所有质数。它基于这样一个原理:从最小的素数开始,将它的所有倍数标记为合数,然后继续找下一个未被标记的数作为新的素数,直到筛选到指定的最大值为止。Python实现时,可以用列表存储数字,并通过循环和条件判断来进行筛选。
以下是简单的Python代码示例:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n+1)
p = 2
while p**2 <= n:
if primes[p] == True:
for i in range(p**2, n+1, p):
primes[i] = False
p += 1
prime_numbers = [p for p in range(2, n) if primes[p]]
return prime_numbers
# 示例
primes = sieve_of_eratosthenes(30)
print(primes)
```
运行这段代码会得到小于30的所有质数。
相关问题
埃拉托色尼筛子python
以下是一个简单的Python程序,用于生成埃拉托色尼筛子:
```python
def sieve(n):
"""
生成埃拉托色尼筛子
"""
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
for j in range(i ** 2, n + 1, i):
primes[j] = False
return [i for i in range(n + 1) if primes[i]]
# 测试
print(sieve(30))
```
输出:
```
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
该程序使用了埃拉托色尼筛子算法,首先创建一个长度为n+1的布尔数组,初始值为True,表示该位置上的数是素数。然后从2开始遍历数组,如果该位置上的数是素数,则将其倍数的位置上的数标记为非素数。最后遍历数组,将所有标记为素数的数存入一个列表中返回。
埃拉托色尼筛求不大于n=25的质数序列 Python
埃拉托色尼筛(Sieve of Eratosthenes)是一种古老而高效的找出一定范围内所有质数的经典算法。以下是使用Python实现一个不超过n(这里设为25)的质数序列的简单版本:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1) # 初始化一个布尔列表,标记所有数字为质数
primes[0], primes[1] = False, False # 0和1不是质数
for i in range(2, int(n**0.5) + 1): # 遍历到n的平方根即可,因为大于这个数的因子一定会小于它本身
if primes[i]: # 如果i是质数
for j in range(i*i, n + 1, i): # 将i的所有倍数标记为非质数
primes[j] = False
# 返回大于1且为质数的索引值对应的数字
return [i for i, is_prime in enumerate(primes) if is_prime and i > 1]
# 输出不大于25的质数序列
print(sieve_of_eratosthenes(25))
阅读全文
相关推荐















