本关任务:编写一个欧拉筛法求素数的小程序。
时间: 2024-10-15 16:19:11 浏览: 24
欧拉项目::telescope:欧拉项目解决方案
欧拉筛法是一种用于找出一定范围内所有素数的高效算法,它利用了每个合数都能表示为若干个较小质数乘积的事实。以下是基于这个原理的一个简单的Python实现:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n+1) # 初始化一个布尔数组,标记每个数字是否为素数,默认认为都是
p = 2 # 首个质数是2
while p**2 <= n:
if primes[p]: # 如果p是素数
for i in range(p**2, n+1, p): # 将p的倍数标记为合数
primes[i] = False
p += 1
# 输出素数列表,不包括非素数的n
prime_numbers = [i for i, is_prime in enumerate(primes) if is_prime and i > 1]
return prime_numbers
# 示例:
n = 50
result = sieve_of_eratosthenes(n)
print(f"小于等于{n}的素数有:{result}")
阅读全文