设计一个函数,输入数字n后,输出n以内的素数。
时间: 2024-09-13 07:11:37 浏览: 104
c代码-输出1000内数值除3余2的素数,10个数字一行,数值间空格__jason整改
设计一个函数用于输出给定数字n以内的所有素数,可以采用经典的“埃拉托斯特尼筛法”(Sieve of Eratosthenes)。这是一种简单而高效的算法,步骤如下:
```python
def sieve_of_eratosthenes(n):
# 初始化一个布尔数组,所有数值初始认为是质数
primes = [True] * (n + 1)
primes[0], primes[1] = False, False # 0和1不是质数
# 从2开始遍历,将2的倍数标记为非质数
for i in range(2, int(n**0.5) + 1):
if primes[i]:
# 将i的倍数标记为非质数
for j in range(i*i, n+1, i):
primes[j] = False
# 输出n以内的所有素数
result = [i for i, is_prime in enumerate(primes) if is_prime]
return result
# 使用示例
n = 30
prime_numbers = sieve_of_eratosthenes(n)
print(f"小于等于{n}的素数有:{prime_numbers}")
阅读全文