算法练习题03：分解质因数

【问题描述】求出区间[a,b]中所有整数的质因数分解,统计一共有多少种不同的分法

【输入格式】输人两个整数a和b。

【输出格式】输出一行,一个整数,代表区间内质因数分解方法之和。

【输入样例】 6 10

【输出样例】 10

【样例说明】 6的质因数为2和3,一共有两个。7的质因数有7,只有一个。8的质因数有2、2、2,一共有三个。9的质因数有3、3,一共有两个。10的质因数有2和5,一共有两个。所以答案为2+1+3+2+2=10。

【数据规模与约定】2<=a<=b<=10000

我的答案：

#include<iostream>
using namespace std;
bool isPrime(int n){int flag = 0;for(int i=n-1;i>1;i--){if(n%i==0){flag++;}}return (flag==0);
}
int main(){int a,b;cin>>a>>b;int dp[10001];int sum=0;for(int i=2;i<=b;i++){if(isPrime(i)){dp[i]=1;}else{for(int j=2;j<i;j++){if(i%j==0){dp[i] = dp[i/j]+dp[j];break;}}}}for(int i=a;i<=b;i++){sum+=dp[i];}cout<<sum;
}

改进点：

1.优化 `isPrime` 函数：

现在的 isPrime 函数效率较低，因为它从 n-1 一直检查到 2。事实上，只需检查到 sqrt(n) 即可。这是因为如果 n 不是质数，它的最小因子一定小于或等于 sqrt(n)。这样可以显著减少不必要的计算。

2. 初始化 `dp` 数组：

建议在一开始将 dp 数组初始化为 0，以避免不确定的初始值导致的错误。

改进后：

#include<iostream>
#include<cmath> // 引入cmath库用于sqrt函数
using namespace std;// 判断是否是质数的函数
bool isPrime(int n) {if (n <= 1) return false;for (int i = 2; i <= sqrt(n); i++) {if (n % i == 0) return false; // 如果 n 能被 i 整除，说明不是质数}return true; // 没有因子，说明是质数
}int main() {int a, b;cin >> a >> b;int dp[10001] = {0}; // 初始化dp数组int sum = 0;for (int i = 2; i <= b; i++) {if (isPrime(i)) {dp[i] = 1; // 如果是质数，dp[i] 设为 1} else {for (int j = 2; j <= sqrt(i); j++) {if (i % j == 0) {dp[i] = dp[j] + dp[i / j]; // 通过因子分解计算质因数的和break; // 找到第一个因子后可以直接退出循环}}}}// 计算从a到b之间所有数的质因数总和for (int i = a; i <= b; i++) {sum += dp[i];}cout << sum; // 输出质因数的总和return 0;
}

老师给的答案：

#include <iostream>
#include <vector>using namespace std;// 判断是否是质数的函数
bool isPrime(int n) {if (n <= 1) {return false; // 1 和更小的数都不是质数}for (int i = 2; i <= n / 2; ++i) {if (n % i == 0) {return false; // 如果能被 i 整除，说明不是质数}}return true; // 如果没有因子，则是质数
}int main() {vector<int> v; // 存储2到b之间的所有质数int a, b;cout << "请输入两个整数 a 和 b，用空格分隔（a < b）：" << endl;cin >> a >> b;// 找出所有在 2 到 b 之间的质数并存储到向量 v 中for (int i = 2; i <= b; ++i) {if (isPrime(i)) {v.push_back(i); // 如果 i 是质数，则存储到向量 v 中}}int sum = 0; // 用于记录质因数的总数// 从 a 开始处理直到 bfor (int i = a; i <= b; ++i) {if (isPrime(i)) {sum++; // 如果 i 是质数，则直接计数} else {// 不是质数时，分解质因数int temp = i; // 暂存 i 的值int index = 0; // 用于遍历质数数组的索引while (temp != 1) { // 当当前数字没有被除尽时if (temp % v[index] == 0) { // 如果能被当前质数整除sum++; // 计数temp /= v[index]; // 更新 temp 为除尽后的值index = 0; // 还原索引，重新从第一个质数（2）开始尝试} else {index++; // 尝试下一个质数}}}}cout << "质因数的总数为：" << sum << endl; // 输出质因数的总数return 0;
}