2015年5月30日 星期六

2015/05/30 Codeforces 546D. Soldier and Number Game

/*
    算質因數個數
    以及前綴合
*/
// http://codeforces.com/problemset/problem/546/D
#include <iostream>
#include <cstdio>

using namespace std;

int pre[6000000];
int fac[6000000];

int T;

int main()
{
    for(int i = 2; i <= 5000000; i++)
    {
        if( fac[i] == 0 )
        {
            pre[i] = 1;

            for(int j = 5000000/i; j >= i; j--)
                fac[i*j] = i;
        }
        else pre[i] = pre[i/fac[i] ]+1;
    }

    for(int i = 2; i <= 5000000; i++)
        pre[i] += pre[i-1];

    scanf("%d", &T);

    while( T-- )
    {
        int a, b;
        scanf("%d %d", &a, &b);

        printf("%d\n", pre[a]-pre[b]);
    }
}

沒有留言:

張貼留言