【问题描述】
求出区间[a,b]中所有整数的质因数分解,统计一共有多少种不同的分法。
[输入格式]
输入两个整数a和b。
[输出格式]
输出一行,一个整数,代表区间内质因数分解方法之和。
[输入样例]
6 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
#include
using namespace std;
int main()
{
int num1,num2,i,count;
while (cin >> num1,num2)
{for(i=num1;i<=num2;i++){
int count1 = 0;
for (int j = 2; j <= i; j++)
{
while (i % j == 0)
{
count1++;
i /= j;
if (i == 1) break;
}
}
if (i > 1) count1++; //若跳出循环之后仍大于1,则还有一个质因数
count+=count1;
}
cout << count << endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int a, b;
int prime[N], min_factor[N];
void init()
{
for (int i = 2; i < N; i ++ )
{
if (!min_factor[i]) prime[min_factor[i] = i] = 1;
for (int j = 1; j <= min_factor[i] && i * j < N; j ++ )
min_factor[i * j] = min_factor[i];
}
}
int main()
{
cin >> a >> b;
init();
int res = 0;
for (int i = a; i <= b; i ++ )
{
int t = i, cnt = 0;
while (t > 1)
{
int p = min_factor[t];
int k = 0;
while (t % p == 0) k ++ , t /= p;
cnt ++ ;
}
res += cnt;
}
cout << res << endl;
return 0;
}