求解最大质因数

ゞ浴缸里的玫瑰 2023-02-20 07:40 20阅读 0赞

### 目录 ###

*  记一道我很喜欢的编程题目
 *   *  知识导入
     *  传统的求最大质因数的方法
     *  总结

# 记一道我很喜欢的编程题目 #

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M 热度指数：5819  
本题知识点： 字符串 数学  
题目描述  
对于给定的字符序列，从左至右将所有的数字字符取出拼接成一个无符号整数（字符序列长度小于100，拼接出的整数小于2^31,），计算并输出该整数的最大素因子（如果是素数，则其最大因子为自身）  
输入描述:  
有多组数据，输入数据的第一行为一个正整数，表示字符序列的数目，每组数据为一行字符序列。  
输出描述:  
对每个字符序列，取出所得整数的最大素因子，若字符序列中没有数字或者找出的整数为0，则输出0，每个整数占一行输出。

示例1  
输入  
3  
sdf0ejg3.f?9f  
?4afd0s&2d79\*(g  
abcde

输出  
13  
857  
0

## 知识导入 ##

**首先对于一个数的质因数你要知道这些：**

*  任何一个数都必然可以表示为许多个素数（质数）的乘积
 *  素数x素数=合数，素数x合数=合数，合数x合数=合数
 *  如果一个合数n有超过√n的质因数，那么有且只有一个，且为自身

***看到这里你可能还是比较蒙圈，没事，待会这几条性质就会一一呈现出威力***

## 传统的求最大质因数的方法 ##

*  **最麻烦的挨个遍历**  
    即先写一个判断是否为质数的函数，然后for(int i=n;i>=2;–i)，只要满足条件i可以被n整除并且i是素数，那么就break，得到最大的质因数。非常慢，直接超时
 *  **稍微有点提高的算法**

int GetMaxPrime(int n) { 
    	int i = 2;
    	int res = 1;
    	while (n > 2) { 
    		if (n%i == 0) { 
    			n /= i;
    			res = i;
    		}	
    		else
    			i++;
    	}
    	return res;
    }

代码的原理就是，从小往大逼近，我不管你n多大，我用一个尽可能小的数，此处是i来一点点剥削你，这样做的目的是，原先你那些比我i大的合数因数，都被我i给瓜分了，造成的结果就是，经过了我的while之后，原先那些可以整除i的合数全部变成了i x i x … x 合数或者素数，也就是说，变成了下面的样子：  
**n=i x i x i x…x 合数或素数 x 合数或素数**  
运气差点的直接成了素数，运气好点的还有其他因数，所以还是合数，所以幸存了。而这样意味着什么呢？其实，他们有一些特征，即素数一定是大于i的，不然早就被i之前的数瓜分了；合数的因数一定是大于i的（除了1），也就是说，不管后面的是合数还是素数，素数的话可能保持不变，除非i的大小=该素数，那么这个素数就化为1了；而合数的话会一定没有比i小的因数，不然早就被i之前的数给剥削掉了，所以它们还能够被后面的i给瓜分成素数，这些素数依然是大于i的，等着i慢慢变大来把他们除为1，直到i等于此时右边仅剩的那个素数，然后n得1，结束。  
我们可以看出，最大的素数其实是一直藏在式子右面的，直到i等于这个数。

*  更快的方法

int max_yinzi(int n)
    { 
        int max =0;
        for(int i=2;i<=int(sqrt(n));i++)//从2到根号n求其质因数
        { 
            while(n%i==0)              //因为一个质因数可能会乘多次，所以应该用while，而不是if
            { 
                max = i;               //让max指向当前最大值
                n /= i;                //除以质因数
            }
            if(n==1)
                break;
        }
        if(n!=1)                       //如果n不等于1，说明存在一个大于根号n的质因数，有且仅有一个，即等于当前的n
            max = n;
        return max;
    }

第三种方法和第二种方法有一些相似之处，但在关键地方有了提高。  
我们注意到，第二种方法终止的条件是n=1，也就是此时i等于最大的那个素数=此时的n，然后一除就得1了，此时停止即可。而第三种方法则不尽然，关键在哪里？？？此时注意**性质3**：

> 如果一个合数n有超过√n的质因数，那么有且只有一个，且为自身

即，这个合数的最大质因数有两种情况：

1.  为本身
2.  小于√n

显然方法2并没有区分这个，而是一股脑的运行下去，其实i超过√n之后都是无用功，不会执行while，而是会一直i++，直到i=此时的n，而其实到√n的时候就已经可以判断是n了，所以这里相当于一个剪枝操作。

注意代码里有个细节，就是for循环的终止条件i<=int(sqrt(n))中，n是变化的，这与上面讲到的一句话是有关系的，即

> 最大的素数是藏在式子右面的，生动一点说，n=i x i x…i x (n/i)（n/i>i）

此时，求n的最大质因数和求n/i的最大质因数是一样的。(n/i)要么是个素数，要么是个合数，是素数则省事了，是合数则还需要进一步的剥削。既然求二者是等效的，那么for循环的条件当然应该朝着更省事的方向去改变，即取n和n/i更小的那个，自然是n/i，那有人可能会问，那既然是求n/i的最大质因数，那是不是应该此时把i置为2，重新开始循环呢，不必，因为对于n/i来说，i1<i的所有剥削操作已经做完了，即，n/i此刻是这么一个数：如果是合数，因数都大于i;如果是素数，则大于i，所以直接从i+1开始继续剥削就行。

## 总结 ##

我的解释可能并不是很容易听懂，我的文字表达能力有限，各位可根据代码，自行领悟，见谅。