质因数分解

深藏阁楼爱情的钟 2023-03-14 05:54 153阅读 0赞

一道清华的复试题，我先后看了两份代码，收获匪浅，分别摘自下面两个博客：

[https://blog.csdn.net/Little\_Kid\_Kang/article/details/88031973][https_blog.csdn.net_Little_Kid_Kang_article_details_88031973]

[https://blog.csdn.net/Zero\_979/article/details/105039355][https_blog.csdn.net_Zero_979_article_details_105039355]

第一个博客我可以看懂，意思很明白，第二个博客涉及到知识盲区了，原来还可以这么简单的做出来：

## 第一份博客的代码： ##

#include <iostream>
    #include <cmath>
    using namespace std;
     
    /*判断是否为质数*/
    bool prime(int N)
    {
    	if (N < 2)
    		return false;
    	if (N == 2)
    		return true;
     
    	int i;
    	for (i = 2; i < sqrt(N); i++)
    	{
    		if (N%i == 0) //i能被j整除，N不是质数
    		{
    			return false;
    		}
    	}
     
    	return true;
    }
     
    /*寻找质因数的个数*/
    int factor_num(int N)
    {
    	int i = 2;
    	int num = 0;
    	while (i < sqrt(N))
    	{
    		if (prime(N))//N为质数，循环退出
    		{
    			num++;
    			break;
    		}
     
    		if (N%i != 0 || !prime(i))//i不是N的因数 || i不是质数
    		{
    			i++;
    			continue;
    		}
     
    		if (prime(i))//i是N的一个质因数
    		{
    			num++;
    			N = N / i;
    			i = 2;
    		}
    	}
     
    	return num;
    }
     
    int main()
    {
    	int N;
    	int i;
     
    	while (cin >> N)
    		cout << factor_num(N) << endl;
     
    	return 0;
    }

比较简单，就是先判断此时的N是不是质因数，是的话代表已经数完了，为什么呢，为什么能保证此时N为质数就一定是最后一个因数呢，也就是说比如有n个质因数，不存在我数到中间的时候，后面因数的乘积是一个质数喽？中间的每次N=N/i，N都是一个非质数嘛？

有两种思路：

1.此时N是质数，不可能再分了，所以停止计算。

2.是的，因为我们数质数的过程是从小的质数开始的，比如120=2\*2\*2\*3\*5，我们会把所有的小质数2都数完再继续往下进行，所以在中间过程中如果N是个非质数，代表还有其他的质数没有被找到，且>=当前的i，所以继续进行，一旦N此时是质数了，表示这就是所能达到的最大的质因数了，不存在更大的质数了，所以输出。

第二步如果不是N的因数或者不是质数，就舍弃，继续往下走。

第三步，i是质数，那么N=N/i，i再从头开始找。

这份代码比较容易理解，那也是因为我之前不知道下面的东西，所以觉得挺好的了。

## 第二种方法： ##

# [Pollard Rho][]因数分解 #

#include<iostream>
    #include<stack>
    #include<cmath>
    using namespace std;
    int main()
    {
        long long int a;
        while(cin>>a)
        {
            stack<int> s;
            for(int i=2;i<=sqrt(a);i++)
            {
                if(a%i==0)
                {
                    s.push(i);
                    a=a/i;
                    i--;
                }
            }
            cout<<s.size()+1<<endl;
        }
        return 0;
    }

当时看了这份代码是蒙圈的，完全不知道为啥，现在看看其实也能理解了。其实一切的一切都是因为是从小到大遍历i的，即便N有很多合数因数，也已经被拆分成更小的质数了，所以上面s.push(i)中的每一个i都是一个质数！很神奇。

[https_blog.csdn.net_Little_Kid_Kang_article_details_88031973]: https://blog.csdn.net/Little_Kid_Kang/article/details/88031973
[https_blog.csdn.net_Zero_979_article_details_105039355]: https://blog.csdn.net/Zero_979/article/details/105039355
[Pollard Rho]: https://www.cnblogs.com/G-M-WuJieMatrix/p/7449974.html