擅长:python、mysql、java
<p>我同意这里提交的另外两个答案,你只需要搜索到数字的平方根。不过,我还有一件事要补充。所提供的解决方案将在合理的时间内为您提供正确的答案。但当问题变得越来越棘手时,你将需要一个更强大的功能。</p>
<p>看看<a href="http://en.wikipedia.org/wiki/Totient" rel="nofollow">Euler's Totient function</a>。尽管它只是间接地应用于这里,但它在以后的问题中非常有用。另一个相关的概念是<a href="http://en.wikipedia.org/wiki/Prime_Factorization" rel="nofollow">Prime Factorization</a>。</p>
<p>改进算法的一个快速方法是找到这个数的素因式分解。在维基百科的文章中,他们以36为例,其主因子分解是2^2*3^2。因此,知道了这一点,你就可以用组合数学来求出36个因子的个数。有了这个,你就不需要计算每一个因子,加上你只需要检查除数2和3就可以了。</p>