[Project Euler] 来做欧拉项目练习题吧: 题目003
周银辉
问题描述：
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
(先思考，如果有兴趣先编程试试，然后才看下面的内容)
问题分析:
这个问题称为"Prime Factorization"(分解质因数)，prime factor称为质因子(或素因子。素数：只能被1和自身整除的整数，不包括1)
比如45而言，其分解后为3*3*5，质因子为3和5
要依次找出这些因子，最简单的方法，就是遍历2,3,4,5,6..k，
如果数n能被k除尽，那么就重复整除它，直到不能除尽为止，然后再用k+1重复上述操作
比如45/2，不能除尽，那么前进到3，45/3=15能除尽，则3是其质因子（想想为什么一定是质数）。
然后继续用3除，15/3=5, 到5/3时不能除尽了，那么前进到下一个数4，不行，再前进到5，5/5=1。
ok，当到达1时，查找结束。
算法可以描述成下面这个样子：
}
为什么说if(n%factor == 0) 成立时，就算找到素因子了呢，这顶多说factor是n的因子呀，比如100/4==0, 但4不是素数？不用担心，因为除数是从2开始从小到大依次查找的，能被4整除的一定能被2整除，所以100在最开始遇到2是就已经被连续除得只剩下25了，所以不存在100/4的情况，顶多存在25/4。
其次，factor++是可以优化的。因为素数除了2之外肯定都是奇数(否则偶数能被2整除就不能叫素数了)，也就是说只有从2过度到3时需要加1，其他时候都是加2
所以 factor++ 可以修改成 factor += (factor==2?1:2)
在加上一条, 顶多有一个factor，使得factor的平方大于n （感谢地狱门神的补充）
注：当完成题目后，对于某些题，官方网站会给出参考答案，在我的博客里不会将官方答案贴出来，仅仅会写下我自己当时的思路，除非两者不谋而合。另外，如果你有更好的思路，请留言告诉我，我非常乐意参与到讨论中来。