求1-1000的素数
时间: 2024-10-10 11:08:46 浏览: 10
求1到1000之间的素数,可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes),这是一种简单而有效的算法。以下是基本步骤:
1. 创建一个长度为1001的布尔数组`isPrime`,并初始化所有元素为`true`,表示每个数字开始都被认为可能是素数。
2. 从2开始(最小的质数),将数组中所有2的倍数标记为非素数(即`isPrime[2*2] = isPrime[4] = false`,然后依次增加到2的平方)。
3. 遍历数组,对于每个未标记为非素数的数(如3),找到它的下一个未被标记的倍数(通常是`i + i`),再次将其标记为非素数。
4. 继续这个过程,直到遍历到√1000左右,因为大于该值的因子已经小于它本身了。
5. 最终剩下的就是素数,因为在筛选过程中,已经被标记为非素数的数肯定不是素数。
下面是Python代码示例:
```python
def find_primes(n):
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return [i for i in range(2, n+1) if primes[i]]
# 找到1到1000之间的素数
prime_list = find_primes(1000)
```
阅读全文