python最快的找素数
时间: 2023-11-08 21:04:54 浏览: 43
Python最快的找素数的方法是使用埃氏筛法,代码如下:
```python
def primes(n):
is_prime = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
_prime[j] = False
return [i for i in range(2, n + 1) if is_prime[i]]
```
这个函数接受一个整数n作为参数,返回小于等于n的所有素数。
相关问题
用python写一个最快的素数筛选
以下是用 Python 编写的最快的素数筛选算法:
```python
def prime_sieve(n):
sieve = [True] * (n // 2)
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i // 2]:
sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]
```
这个算法的时间复杂度为 O(n log log n),可以在较短的时间内计算出较大的素数。
Python 200ms输出素数个数
以下是一个可能的解决方案:
```python
import time
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
start_time = time.time()
count = 0
for i in range(2, 100000):
if is_prime(i):
count += 1
end_time = time.time()
print('素数个数:', count)
print('运行时间:', end_time - start_time, '秒')
```
这个程序首先定义了一个名为`is_prime`的函数,用于判断一个数是否为素数。然后,它使用一个循环遍历从2到100000的所有整数,并使用`is_prime`函数检查每个整数是否为素数。最后,它打印出素数的数量和程序的运行时间。
注意,这个程序可能需要更长的时间才能完成,具体取决于你的计算机性能。如果你想更快地计算素数,请尝试使用更高效的算法,例如筛选法。