Factorization
题目描述
根据质因子唯一分解定理可知n=pk11pk22…pkmm,其中pi都是质数。我们定义f(n)=m, 求g(a,b)=∑bi=af(i)。
输入
第一行是一个整数T(1≤T≤1000),表示样例的个数。
以后每个样例占一行,为两个整数 a(2≤a≤b≤106)。
输出
依次每行输出一个样例的结果,为一个整数。
样例输入
2
2 2
2 10
样例输出
1
11
AC代码
#include<stdio.h>
#define N 1000005
int a[N]={};
int f[N]={};
void init(){
int i,j,cnt=0;
a[0]=1,a[1]=1;
for(i=2;i*i<=N;i++){
if(a[i]==0){
for(j=2*i;j<=N;j+=i){
a[j]=1;
}
}
}
for(i=2;i<=N;i++){
if(a[i]==0){
f[i]=1;
for(j=2;i*j<=N;j++){
f[i*j]++;
}
}
f[i]+=f[i-1];
}
}
void sol(){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",f[b]-f[a-1]);
}
int main()
{
int T;
scanf("%d",&T);
init();
while(T--){
sol();
}
}
解题思路:埃筛筛选素数,如果i为素数,则素因子个数为1。此题的巧妙处在于f[i*j]++。比如f[6],f[2]=1,f[2*3]=1;f[3]=1,f[2*3]=1,所以f[6]=2。本题还利用前缀和知识。