TCO2012 Round1A Medium(500) EllysFractions

EllysFractions

例えば、6!=720は、720=2⁴×3²×5と素因数分解できる。これを既約分数の分子と分母に分けるとき、2を分子に8を分母にということはできず、それぞれの素数ごとに分子か分母かを選ぶことになる。それは、2⁴通り。分子が分母より小さい分数はちょうどその半分。n!の素因数の個数は、n以下の素数の個数と等しい。

class EllysFractions{public:
long long getCount( int N )
{
    long long ans = 0;
    long long P = 0;

    for ( int i=2; i<=N; i++ )
    {
        bool f = true;
        for ( int j=2; j<i; j++ )
            if ( i%j==0 )
                f = false;
        if ( f )
            P++;
        ans += 1LL<<(P-1);
    }

    return ans;
}};