CFR 546 D. Soldier and Number Game ( 素数分解 )

http://codeforces.com/contest/546/problem/D
用質數預處理的方法快速計算每個值可以分解成多少質因數。

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 1e6 + 6;
const int MAXAB = 5e6 + 6;
typedef long long ll;

ll ps[ MAXAB ];

int val[ MAXAB ], cnt[ MAXAB ];
int not_prime[ MAXAB ];

void prePrime(){
    not_prime[ 1 ] = 1;
    for(int i = 2; i <= 5000000; ++i){
        if( not_prime[ i ] ) continue;
        for(int j = i; j <= 5000000; j += i){
            not_prime[ j ] = 1;
            while( val[ j ] % i == 0 )
                val[ j ] /= i, ++cnt[ j ];
        }
        not_prime[ i ] = 0;
    }
}

void preSolve(){
    for(int i = 1; i <= 5000000; ++i)
        val[ i ] = i;
    prePrime();
    for(int i = 2; i <= 5000000; ++i){
        assert( val[ i ] >= 1 );
        ps[ i ] = ps[ i - 1 ] + cnt[ i ];
    }
}

int main(){
    preSolve();
    int T; scanf("%d", &T);
    while( T-- ){
        int a, b; scanf("%d%d", &a, &b);
        // printf("%lld %lld\n", ps[ a ], ps[ a - b ]);
        printf("%I64d\n", ps[ a ] - ps[ b ]);
    }
    return 0;
}