C++实现给定n个正整数每个正整数都包含若干种质因子现在小明想知道这些质因子中哪种质因子出现的次数最多注意每个数字中出现的每种质因子只统计一次？输入描述输入数据共两行。第一行包含一个整数n表示数字个数。第二行包含以空格隔开的n个整数每个数字在2~100000之内。输出描述输出一个正整数表示出现最多的质因子如果有多个质因子出现一样多输出最小的那一个。样例1输入42 6 8 10输出2

算法1

这道题可以用线性筛法将所有质因数筛出来，然后在统计每个质因数在这些数字中出现的个数。

时间复杂度

• 线性筛法求出所有质因数的时间复杂度为 $O(n\log\log n)$。
• 统计每个质因数个数的时间复杂度为 $O(nm)$，其中 $m$ 为质因数的个数。
• 故总时间复杂度为 $O(n\log\log n+nm)$。

C++ 代码

算法2

我们可以用一个 unordered_map 记录每个质因子出现的次数，最后再遍历一遍 unordered_map，找出出现次数最多的质因子即可。

时间复杂度

• 预处理每个数的质因数的时间复杂度为 $O(n\log \log n)$。
• 统计每个质因数个数的时间复杂度为 $O(nm)$，其中 $m$ 为质因数的个数。
• 统计最大质因数的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n\log\log n+nm+n) = O(n\log\log n+ nm)$。

C++ 代码

参考文献

https://www.acwing.com/solution/content/26311/