Factorization

题目描述

根据质因子唯一分解定理可知n=pk11pk22…pkmm，其中pi都是质数。我们定义f(n)=m, 求g(a,b)=∑bi=af(n)。

输入

第一行是一个整数T(1≤T≤1000)，表示样例的个数。

以后每个样例占一行，为两个整数 a(2≤a≤b≤106)。

输出

依次每行输出一个样例的结果，为一个整数。

样例输入

2
2 2
2 10

样例输出

1
11

#include
#include
int a[1000000]={0};
int b[1000000]={0};
int main()
{int i,j,g,c[78500];for(i=2;i<=1000000;i++){if(a[i]==0){for(j=2*i;j<=1000000;j+=i){a[j]++;}}}for(i=2,g=0;i<=1000000;i++)//c数组是素数表 {if(a[i]==0){c[g]=i;g=g+1;}}for(i=0;i<78500;i++){for(j=1;j*c[i]<=1000000;j++){b[j*c[i]]++;}}//b数组每个数带标所含素数个数for(i=3;i<=1000000;i++){b[i]+=b[i-1]; } int T;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);printf("%d\n",b[m]-b[n-1]);}
}

这道题就是打表做的，还以为会超时居然没有

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！