当先锋百科网

首页 1 2 3 4 5 6 7

Python求素数的过程一般可以使用for循环来实现,但是随着素数的增加,我们会发现计算速度变得越来越慢。因此,我们需要优化算法,以提高执行效率。

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num ** 0.5) + 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

print(get_primes(10000))

python求素数 优化

以上代码中,我们使用了is_prime函数来判断是否是素数。该函数使用了for循环,枚举了从2到n开方向下取整的数,判断是否能被整除。

我们可以进一步优化该算法,将枚举范围从2到n开方缩小为2到该数的一半。因为如果该数不是素数,最小的质因子也不可能超过其一半。

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, num // 2 + 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

print(get_primes(10000))

通过这种方式优化,我们可以大大缩短计算时间,从而更有效地求取素数。