用除余法二维数组找素数
时间: 2023-12-09 14:50:56 浏览: 42
除余法是一种快速判断质数的方法,但不是用于找素数的方法。如果要用二维数组找素数,可以使用埃氏筛法(Sieve of Eratosthenes)。
具体实现方法如下:
1. 创建一个二维数组,表示从 2 到 n 的所有整数,初始值都为 true。
2. 从 2 开始,将数组中所有 2 的倍数(除 2 本身)标记为 false。
3. 继续取下一个未被标记的数,将数组中所有该数的倍数(除该数本身)标记为 false。
4. 重复步骤 3,直到取数大于 n 的平方根。
5. 数组中所有值为 true 的下标即为素数。
下面是具体的代码实现:
```python
def find_primes(n):
# 创建一个二维数组,初始值都为 True
primes = [[True for j in range(n+1)] for i in range(n+1)]
# 将 0 和 1 标记为 False
primes[0][0] = primes[0][1] = False
for i in range(2, int(n**0.5)+1):
if primes[i][i]:
# 将 i 的倍数(除 i 本身)标记为 False
for j in range(i*2, n+1, i):
primes[i][j] = False
# 打印出所有素数
for i in range(2, n+1):
if primes[i][i]:
print(i, end=' ')
```
这个方法的时间复杂度为 O(n log log n),比暴力枚举的 O(n^2) 要快很多。