[已解决]python_p49讲课后作业问题求助

天下有敌

小甲鱼Python  P49 课后作业最后一题
下面这个  is_prime  方法里面的 for 循环有什么用？谁讲解一下呗。。  为什么要 根+1？

import math

def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for current in range(3, int(math.sqrt(number) + 1), 2):
            if number % current == 0:
                return False
        return True
    return False

def get_primes(number):
    while True:
        if is_prime(number):
            yield number
        number += 1

def solve():
    total = 2
    for next_prime in get_primes(3):
        if next_prime < 2000000:
            total += next_prime
        else:
            print(total)
            return

if __name__ == '__main__':
    solve()

最佳答案

月排行榜 / 总排行榜

Twilight6

2020-6-20 09:11:22

天下有敌 发表于 2020-6-20 09:04
我问的是 is_prime函数里面的 for 循环

这属于算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。
素数是只有1和本身能整除的整数。所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。举例说明：
25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。
这样做可以减少循环次数，素数是因子为1和本身， 如果数c不是素数，则还有其他因子，其中的因子，假如为a,b.其中必有一个大于sqrt(c) ，一个小于sqrt(c) 。所以m必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。

再比如：24的因数有1、2、3、4、6、8、12、24
按定义应该用2－23去除，但经过分析上面的数可以发现
1×24、2×12、3×8、4×6
如果2、3、4是某个数的因数，那么另外几个数也是，反之也一样
所以为提高效率，可以只检查小于该数平方根的那些数，如24的平方根大于4小于5，检查2－4就可以了！

这个有关于算法，开根号计算素数能很大的提高去重率，+1是因为 range 是左开右闭的，右闭是取不到你最后计算的数值，+1 后就取的到了，你看看上面的资料吧

跳转到最佳答案楼层

Twilight6

def get_primes(number):
    while True:
        if is_prime(number):
            yield number
        number += 1

是指这个吗？？？你如果不 +1 会导致死循环呀

一直循环同一个 number 导致 if is_prime(number) 条件永远不会成立

txxcat

求素数，电脑的办法就是看能不能被2以上的所有的数给整除了，这就涉及到除数的范围，最笨的方法就是从2到自己-1，反正电脑速度快，爱算不算；第二笨的方法是从2到自己除2取整，运算量比第一笨少了一半（这是我没开窍时的做法），但是效率还是不够高；那么优化算法就是2到平方根取整了，为什么这么算呢？举个例子105，能被3，5，7，15，21，35整除，实际上，可以分成3*35，5*21，7*15这几组，当然1*105也是，不过不算在这里了，那么你算了3没必要算35，算了5没必要算21，算了7没必要算15，那么要找到临界点，再举个例子，81，因子有3，9，27，其中的9，只能和9乘才是81，也就是说9是81的临界点，就是81的平方根，再回头算算105的平方根去整是10，可以看到分割了3、5、7和15、21、35，这就是为什么范围上限是平方根了，至于为什么+1，这个是range的特性了（我也不喜欢这个特性，刚开始容易忘）。

qiuyouzhi

for循环就是遍历2-N的根，大于n的根是不可能被n整除的。
sqrt+1是为了向上取整。

天下有敌

Twilight6 发表于 2020-6-19 23:13
是指这个吗？？？你如果不 +1 会导致死循环呀

一直循环同一个 number 导致 if is_prime(number) 条 ...

我问的是 is_prime函数里面的 for 循环

Twilight6

天下有敌 发表于 2020-6-20 09:04
我问的是 is_prime函数里面的 for 循环

这属于算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。
素数是只有1和本身能整除的整数。所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。举例说明：
25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。
这样做可以减少循环次数，素数是因子为1和本身， 如果数c不是素数，则还有其他因子，其中的因子，假如为a,b.其中必有一个大于sqrt(c) ，一个小于sqrt(c) 。所以m必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。

再比如：24的因数有1、2、3、4、6、8、12、24
按定义应该用2－23去除，但经过分析上面的数可以发现
1×24、2×12、3×8、4×6
如果2、3、4是某个数的因数，那么另外几个数也是，反之也一样
所以为提高效率，可以只检查小于该数平方根的那些数，如24的平方根大于4小于5，检查2－4就可以了！

这个有关于算法，开根号计算素数能很大的提高去重率，+1是因为 range 是左开右闭的，右闭是取不到你最后计算的数值，+1 后就取的到了，你看看上面的资料吧

天下有敌

Twilight6 发表于 2020-6-20 09:11
这个有关于算法，开根号计算素数能很大的提高去重率，+1是因为 range 是左开右闭的，右闭是取不 ...

万分感谢，每次问问题都有你，真是辛苦你了。我怀疑你是住在鱼c论坛

Twilight6

天下有敌 发表于 2020-6-20 10:31
万分感谢，每次问问题都有你，真是辛苦你了。我怀疑你是住在鱼c论坛

  不辛苦 不辛苦~~