[Project Euler] 来做欧拉项目练习题吧: 题目003

时间:2023-02-22 22:53:47

                                [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时,查找结束。 

算法可以描述成下面这个样子:

void test(int n)
{
int factor = 2;     //从2开始查找
while(n>1)
{
if(n%factor == 0)
{
//test
printf("prime factor:%d\n", factor);
while(n%factor == 0)
{
n /= factor;
}
}
factor++; //这里可以被优化,见下文
}

为什么说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 (感谢地狱门神的补充

 

注:当完成题目后,对于某些题,官方网站会给出参考答案,在我的博客里不会将官方答案贴出来,仅仅会写下我自己当时的思路,除非两者不谋而合。另外,如果你有更好的思路,请留言告诉我,我非常乐意参与到讨论中来。