xtu oj 1377 Factorization

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。本题还利用前缀和知识。