开方标记法求200000以内素数
时间: 2024-05-08 10:11:15 浏览: 17
以下是使用开方标记法求200000以内素数的Python代码:
```python
import math
n = 200000
prime = [True] * (n+1)
prime[0] = prime[1] = False
for i in range(2, int(math.sqrt(n))+1):
if prime[i]:
for j in range(i*i, n+1, i):
prime[j] = False
result = [i for i in range(n+1) if prime[i]]
print(result)
```
代码解释:
首先,我们定义了一个长度为n+1的布尔型数组prime,用于标记每个数是否为素数。由于0和1不是素数,因此我们将prime和prime都标记为False。
接下来,我们从2开始遍历到sqrt(n),如果当前数i是素数,则将i的倍数j标记为非素数。具体来说,我们从i*i开始,每次加i,直到大于n。
最后,我们遍历整个数组,将所有标记为素数的数加入到结果列表result中,并将其输出。
相关问题
python函数法求200000以内素数
以下是使用函数法求200000以内素数的Python代码:
```python
import math
def is_prime(num):
"""
判断一个数是否为素数
"""
if num < 2:
return False
for i in range(2, int(math.sqrt(num))+1):
if num % i == 0:
return False
return True
def get_primes(n):
"""
获取小于等于n的所有素数
"""
primes = []
for i in range(2, n+1):
if is_prime(i):
primes.append(i)
return primes
print(get_primes(200000))
```
埃氏筛求200000以内素数
以下是使用埃氏筛法求200000以内素数的Python代码:
```python
def prime_sieve(n):
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = 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
return [x for x in range(n+1) if is_prime[x]]
primes = prime_sieve(200000)
print(primes)
```
运行结果为一个包含所有200000以内素数的列表。