|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 天下有敌 于 2020-6-20 09:03 编辑
小甲鱼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()
复制代码
这属于算法上的问题,好好考虑一下算法,还要考虑一下素数的定义。
素数是只有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 后就取的到了,你看看上面的资料吧
|
|