Google – All Prime Factors of N
给一个数n，找出它所有的prime factor
[Solution]
首先无论n是多少，得把2去掉，去掉之后n必然是一个奇数。
然后从3开始，一直到sqrt(n)，挨个找prime factor，increment by 2，因为偶数不可能是prime number。
至于为什么到sqrt(n)就可以停止，可以这么来证明，假设a和b是n的prime factor，那么a * b = n，如果a和b都大于sqrt(n)，那么他们的乘积必然大于n。
所以不可能有两个或两个以上的prime factor大于sqrt(n)的情况。
最后如果n本身就是一个prime number，需要把它自己加入到result list里。
Read full article from Google – All Prime Factors of N
No comments:
Post a Comment