uva 11762

<pre name="code" class="cpp">#include <bits/stdc++.h>

using namespace std;
#define maxn 1000000+10

bool isprime[maxn];
int  mark[maxn];
double dp[maxn];
int T, n;

void make_prime(int num)
{
    int tmp=sqrt(num+0.5);
    memset(isprime,true,sizeof(isprime));
    for(int i=2; i<=tmp; i++)
        if(isprime[i])
            for(int j=i*i; j<=num; j+=i)
                isprime[j]=false;
    isprime[0] = false;
    isprime[1] = false;

    int cnt = 0;
    for(int i=2; i<=num; i++)
        if(isprime[i]) mark[i] = ++cnt;
        else mark[i] = cnt;
}

double solve(int m)
{
    int k = 0;
    if(m == 1) return 0;

    if(dp[m]) return dp[m];
    for(int i=2; i<=m; i++)
        if(isprime[i] && m%i == 0)
            {
                dp[m] += solve(m/i)/mark[m];
                k++;
            }

    dp[m] += mark[m]/(double)k;
    return dp[m];
}


int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin>>T;
    make_prime(maxn);
    while(T--)
    {
        memset(dp, 0, sizeof(dp));
        cin>>n;
        double ans = solve(n);
        printf("%.10lf\n", ans);
    }
    return 0;
}

uva 11762

原文：http://blog.csdn.net/dojintian/article/details/44519301