计挑-C++-20-编程4()

题目描述
有N个正整数，求这N个正整数两两之间的公共质因数之和。

输入说明
第1行：正整数N(N<100)
第2行: N个空格分隔的正整数(每个元素<10000)
输出说明
输出这N个正整数两两之间的公共质因数之和，结果对1000000007取模。
输入样例
4
4 6 8 9
输出样例
11

输入说明
第1行：正整数N(N<100)
第2行: N个空格分隔的正整数(每个元素<10000)
输出说明
输出这N个正整数两两之间的公共质因数之和，结果对1000000007取模。
输入样例
4
4 6 8 9
输出样例
11

跟给的资料里不太一样，资料里说的是“最大公约数之积”，我觉得这个更难些

公共质因数：公共因数，同时要是质数

公共质因数：公共因数，同时要是质数

万一有多个公共质因数怎么算？加起来

关键在于：

  • 怎么求两个数的公共质因数？
  • 挨个做的话会不会效率太低，而且是组合问题，有没有更巧妙的思路？

分解质因数的算法…我觉得判断是不是质数就有点麻烦了

————————

题目描述
有N个正整数，求这N个正整数两两之间的公共质因数之和。

输入说明
第1行：正整数N(N<100)
第2行: N个空格分隔的正整数(每个元素<10000)
输出说明
输出这N个正整数两两之间的公共质因数之和，结果对1000000007取模。
输入样例
4
4 6 8 9
输出样例
11

输入说明
第1行：正整数N(N<100)
第2行: N个空格分隔的正整数(每个元素<10000)
输出说明
输出这N个正整数两两之间的公共质因数之和，结果对1000000007取模。
输入样例
4
4 6 8 9
输出样例
11

跟给的资料里不太一样，资料里说的是“最大公约数之积”，我觉得这个更难些

公共质因数：公共因数，同时要是质数

公共质因数：公共因数，同时要是质数

万一有多个公共质因数怎么算？加起来

关键在于：

  • 怎么求两个数的公共质因数？
  • 挨个做的话会不会效率太低，而且是组合问题，有没有更巧妙的思路？

分解质因数的算法…我觉得判断是不是质数就有点麻烦了