编写一个Python函数P = getPrimes(M), 以计算出小于等于1000000的全体素数,并为你的程序运行时间计时。
时间: 2024-12-22 08:12:15 浏览: 11
当然可以。在Python中,我们可以编写一个名为`getPrimes`的函数,用于生成指定范围内的素数。首先,我们需要一个高效的素数判断算法,例如埃拉托斯特尼筛法(Sieve of Eratosthenes),然后我们可以在主程序中使用`time`模块来测量函数运行时间。
下面是一个简单的实现:
```python
import time
def is_prime(n):
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
def get_primes(M):
primes = []
start_time = time.time()
for num in range(2, M+1):
if is_prime(num):
primes.append(num)
end_time = time.time()
print(f"Found {len(primes)} primes under {M} in {end_time - start_time:.6f} seconds.")
return primes
# 计算小于等于1000000的素数并记录时间
P = get_primes(1000000)
```
在这个例子中,`is_prime`函数用于检查数字是否为素数,而`get_primes`函数则遍历从2到`M`的所有数字,筛选出素数,并打印出找到的素数总数以及所花费的时间。
阅读全文