判断素数: 编写一个函数,输出大于0小于100的所有素数。素数是指只能被1和自身整除的大于1的自然数。例如,7是素数,而8不是。
时间: 2024-11-15 09:30:52 浏览: 48
判断素数的基本算法通常被称为“埃拉托斯特尼筛法”(Sieve of Eratosthenes),这个过程涉及创建一个列表,然后逐步排除所有非素数。以下是简单的步骤:
1. 创建一个布尔数组`isPrime[0..n]`,其中`n`是要检查的最大数。初始化所有元素为`true`,表示它们都是潜在的素数。
2. 从2开始,遍历到`sqrt(n)`(因为大于这个数的因子肯定有一个小于等于它本身)。对于每个素数`p`:
- 如果`isPrime[p]`是`true`,那么它是素数,将它的倍数标记为非素数。即设置`isPrime[p*i] = false`(`i`从2开始递增,直到超过`n/p`)。
3. 遍历`isPrime`数组,将所有值为`true`的位置对应的数字添加到结果集合中。
下面是Python的一个简单实现:
```python
def primes_up_to_n(n):
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False # 0和1不是素数
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(2, n) if is_prime[i]]
# 输出大于0且小于100的所有素数
print(primes_up_to_n(100))
阅读全文
相关推荐



















