求2-100的质数算法
时间: 2024-10-16 22:22:16 浏览: 18
算法课设--求素数问题
5星 · 资源好评率100%
求2到100之间的质数,可以使用著名的“埃拉托斯特尼筛法”(Sieve of Eratosthenes)。这是一种简单而有效的找出一定范围内所有质数的算法步骤:
1. 创建一个从2开始、长度为101的布尔数组isPrime,初始值全部设为True,表示所有数字都是潜在的质数。
2. 遍历数组,从第一个非质数(即2)开始,将其标记为False。因为除了2以外,其他的偶数都不是质数。
3. 对于当前遍历到的每个质数i,将它的所有倍数(i * i到100的整数倍,由于之前已经处理了偶数,所以这里可以从i * i开始)都标记为非质数。这一步完成之后,数组中未被标记的数字就是质数。
4. 继续下一个未被标记为非质数的数,直到遍历完所有的数。最后剩下的isPrime数组中,索引位置对应的值为True的就是2到100范围内的质数。
以下是简单的Python代码实现这一算法:
```python
def find_primes(n):
is_prime = [True] * (n+1)
is_prime[0], is_prime[1] = False, False
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
primes = [i for i, prime in enumerate(is_prime) if prime]
return primes
primes_in_range = find_primes(100)
阅读全文