|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
导入了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
为什么要这么做呢？？？
这属于算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。
素数是只有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 后就取的到了，你看看上面的资料吧
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2020-6-20 09:22:35
置顶卡
千斤顶
显身卡
发表于 2020-6-20 09:23:16
楼主
发表于 2020-6-20 10:38:21
