代码之家 › 专栏 › 技术社区 › Partho63 BASANT KUMAR

质数的python函数

primes python-3.x python

Partho63 BASANT KUMAR · 技术社区 · 7 年前

我想写一个函数,它返回一个素数的个数,这个素数存在于一个给定的数之前,并且包括一个给定的数。函数计数\素数(100)应返回25

我写了一个代码,它给出23而不是25。函数跳过41和71,同时计算1到100之间的所有其他素数。有人能解释为什么我的代码跳过41和71吗?我的代码是

import math
def count_primes(num):
    current_number = 4
    number_of_prime = 2
    while current_number <= num:
        is_prime = True
        if current_number%2==0:
            is_prime = False
            current_number += 1
            continue
        else:
            limit = math.ceil(current_number ** 0.5)+1
            for i in range(3, limit, 2):
                if current_number%i==0:
                    is_prime = False
                    current_number += 1
                    continue
        if is_prime == True:
            print(current_number)
            number_of_prime += 1
        current_number += 1
    return number_of_prime
count_primes(100)

我写了另一个函数,它工作得很好。我只想知道为什么这个代码只跳过41和71。

2 回复 | 直到 7 年前

David Z 7 年前

问题在于你的内环:

for i in range(3, limit, 2):
    if current_number%i==0:
        is_prime = False
        current_number += 1
        continue

这个 continue 这里的语句只继续内部循环,而不是外部循环。这意味着无论何时测试一个复合数字,它都会增加 current_number 但它并没有回到测试2的可除性。

例如,在以 current_number == 39 代码发现它可以被3整除,所以它递增 当前号码 到40,继续内部循环,而不是外部循环。所以它测试40的可除性是5,而不是3。因为40可以被5整除,所以它继续测试41是否可以被7整除。当然41不能被7整除,但是 is_prime 仍然是 False 当代码发现39可以被3整除时,41就不会被打印出来。

这是一种非常特殊的情况组合,只会在您测试的范围内影响41和71,因为它们遵循几个相当大的复合数字序列,即39、40和69、70。

我建议你自己做一个练习:把打印语句放在测试可分割性的地方,你会清楚地看到会发生什么。例如:

print('testing {} for divisibility by 2: {}'.format(current_number, current_number % 2 == 0))
if current_number%2==0:
    is_prime = False
    ...

后来

print('testing {} for divisibility by {}: {}'.format(current_number, i, current_number % i == 0))
if current_number%i==0:
    ...

Corentin Limier 7 年前

修复了代码并添加了注释:

import math
def count_primes(num):
    current_number = 4
    number_of_prime = 2
    while current_number <= num:
        is_prime = True
        if current_number%2==0:
            is_prime = False
            current_number += 1
            continue
        else:
            limit = math.ceil(current_number ** 0.5)+1
            for i in range(3, limit, 2):
                if current_number%i==0:
                    is_prime = False
                    #current_number += 1 #first increment
                    continue
                    #This continue statement does not skip the next lines (after the for loop) so you increment current_number twice
        if is_prime == True:
            print(current_number)
            number_of_prime += 1
        current_number += 1 #second increment
    return number_of_prime
count_primes(100)