XTU 1377 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

思路:打表

清晰的AC代码如下：

#include 
#define N 1000010
using namespace std;
int ch[N+10],a[N+10],sum[N+10];//素数打表，质因子打表，求和打表
int main()
{ch[1]=1;ch[2]=0;int i,j;for(i=2;i*i<=N;i++){//素数打表，0是素数if(!ch[i]){for(j=i*i;j<=N;j+=i){ch[j]=1;}}}for(i=2;i<=N;i++){//如果是质数那么p只有1个if(ch[i]==0){a[i]=1;}}for(i=2;i<=N;i++){for(j=2;j*i<=N;j++){if(!ch[i]){//定i为质因子，j你别管就单单当做一个乘数来看待，我们主要以i为质因子a[i*j]++;}}}for(i=2;i<=N;i++){sum[i]=sum[i-1]+a[i];//求和}int t;cin>>t;while(t--){int a,b;cin>>a>>b;cout<

#include 
#include 
#define N 1000010
using namespace std;
int ch[N+10],a[N+10];
int main()
{memset(a,0,sizeof(a));ch[1]=1;ch[2]=0;int i,j;for(i=2;i*i<=N;i++){if(!ch[i]){for(j=i*i;j<=N;j+=i){ch[j]=1;}}}for(i=2;i<=N;i++){//2853708if(!ch[i]){a[i]=1;for(j=2;j*i<=N;j++){a[i*j]++;}}a[i]+=a[i-1];}int t;cin>>t;while(t--){int c,b;cin>>c>>b;cout<

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