Python中从键盘输入一个整数n,找出小于n的所有素数。
时间: 2024-09-30 15:04:12 浏览: 37
算法领域-输出n以内的所有的素数-python实现
在Python中,你可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来找出所有小于给定整数n的素数。这是一个古老而有效的算法,步骤大致如下:
1. 创建一个列表,长度为n+1,并将所有元素初始化为True,表示它们都是潜在的素数。
2. 从2开始,遍历到sqrt(n),对于每个素数i,如果它已经被标记为素数(列表[i]为True),那么就将它的倍数(除了它本身)都标记为合数(列表[j*i]设为False,其中j > 1)。
3. 遍历完成后,列表中索引为[2, n)的部分包含的就是所有小于n的素数。
这里是相应的Python代码示例:
```python
def find_primes(n):
primes = [True for _ in range(n + 1)]
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
# 输出小于n的素数
for p in range(2, n):
if primes[p]:
print(p)
# 获取用户输入
n = int(input("请输入一个正整数:"))
find_primes(n)
```
当你运行此程序并输入一个整数,比如50,它会打印出小于50的所有素数。
阅读全文