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++){//2853708
        if(!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<