列出N以内所有素数:输入一个大于2的整数,输出该数内所有素数
时间: 2024-10-24 19:18:31 浏览: 30
java代码-输入N,输出大于N的质数
列出N以内所有素数是一个经典的算法问题,通常可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来解决。这个方法的基本思想是从2开始,将它的倍数标记为合数,然后找出下一个未被标记的数(即下一个素数),重复这个过程直到达到给定的最大值N。
以下是Python的一个简单实现:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
return [i for i in range(2, n + 1) if primes[i]]
# 示例
n = int(input("请输入一个大于2的整数:"))
result = sieve_of_eratosthenes(n)
print(f"{n}以内的所有素数有:", result)
阅读全文