在Python中,求质数可以通过多种方法实现,以下是几种常见的方法:
方法一:穷举法
```python
def countPrimes1(n):
if n <= 2:
return 0
res = []
for i in range(2, n):
flag = 0
for j in range(2, i):
if i % j == 0:
flag = 1
break
if flag == 0:
res.append(i)
return len(res)
方法二:利用定理优化
```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):
primes = []
for i in range(2, n):
if is_prime(i):
primes.append(i)
return primes
方法三:埃拉托斯特尼筛法
```python
def sieve_of_eratosthenes(n):
sieve = [True] * (n + 1)
sieve = sieve = False
for i in range(2, int(math.sqrt(n)) + 1):
if sieve[i]:
for j in range(i * i, n + 1, i):
sieve[j] = False
return [i for i in range(2, n + 1) if sieve[i]]
方法四:使用生成器
```python
def prime_generator(n):
for num in range(2, n + 1):
if all(num % i for i in range(2, int(math.sqrt(num)) + 1)):
yield num
方法五:使用filter函数
```python
def func_get_prime(n):
return filter(lambda x: not any(x % i == 0 for i in range(2, int(math.sqrt(x)) + 1)), range(2, n + 1))
以上方法均可用来找出指定范围内的所有质数。你可以根据具体需求选择合适的方法。需要注意的是,随着n的增大,计算质数所需的时间和资源也会增加,因此对于较大的n值,可能需要考虑更高效的算法