质因数个数-蓝桥杯算法题PYTHON数据结构
题目
解题思路
常规解题思路是设置两个循环，第一个循环判断是否是质数，第二个循环判断是否是约数。但是这样的话两个循环遇见较大的数时比较容易出现超时的情况，所以我们现在要想一个更简单的办法。
1.所有数都可以由质数的乘积表示
例如
36=2*2*3*3
105=3*5*7
2.一个数的因数也都可以被分解为质数的乘积，例如36的因数6
6=2*3
我们就可以只设置一个循环这个数从2开始循环条件是他的平方要小于所给的数
当所给的数除以循环的这个数时余数为0时则进入下一个循环把它除尽掉。
代码
n = int(input())ans = 0i = 2while i * i <= n:if n % i == 0:ans += 1while n % i == 0:n = n/ii += 1if n > 1:ans += 1print(ans)当余下的n大于1时说明没被质数除尽，也就是本身就是质数所以要加1
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！