xtu oj 1396 函数

题目描述

根据质因子唯一分解定理可知

n=∏i=1mpkii

，其中?pi?都是素数。

定义?g(n)=∑mi=1ki?， 求?∑bi=ag(i)?。

输入

第一行是一个整数T(1≤T≤10000)，表示样例的个数。 以后每行两个整数a,b(1≤a≤b≤106)

输出

每行输出一个样例的结果。

样例输入

2
1 2
1 1000000

样例输出

1
3626619

AC代码

#include<stdio.h>
#define N 1000005
int a[N]={};
int f[N]={};
void init(){
	//埃筛
	a[0]=1,a[1]=1;
	int i,j,cnt=0;
	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[j];	
			}
	 }
	}
	for(i=1;i<=N;i++)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();
	}
 } 

与前面1377那道题类似。未求和前f[2]=1,f[4]=f[2]+f[2]=2,f[8]=f[2]+f[4]=3。找到规律?f[i*j]=f[i]+f[j]? ?