Dilu have learned a new thingabout integers, which is - any positive integer greater than 1 can be divided byat least one prime number less than or equal to that number. So, he is nowplaying with this property. He selects a numberN. And he calls this D.

In each turn he randomly chooses aprime number less than or equal to D.IfD is divisible by the prime numberthen he divides D by the primenumber to obtain newD. Otherwise hekeeps the old D. He repeats thisprocedure untilD becomes 1. What isthe expected number of moves required for Nto become 1.

[We say that an integer is said tobe prime if its divisible by exactly two different integers. So, 1 is not aprime, by definition. List of first few primes are 2, 3, 5, 7, 11, …]

Input

Input will start with an integer T (T <= 1000), which indicates the number of test cases. Each ofthe nextT lines will contain oneinteger N (1 <= N <= 1000000).

Output

For each test case output a single line giving the casenumber followed by the expected number of turn required. Errors up to 1e-6 willbe accepted.

SampleInput                             Outputfor Sample Input

Problemsetter: Md. Arifuzzaman Arif

Special Thanks: Sohel Hafiz

题意：给你一个整数N，每次都可以在不超过N的素数中随机选择一个P，如果P是N的约数，则把N变成N/P，否则N不变，问平均情况下要多少次随机选择，才能把N变成1

思路：设f(i)表示当前的数为i时接下来需要选择的次数，这样我们就能得到一个方程，例如：f(6)=1+f(6)+1/3+f(3)*1/3+f(2)*1/3

我们设不超过x的素数有p(x)个，其中有g(x)个是x的因子，则f(x) = 1 + f(x)*(1-g(x)/p(x)) + f(x/y)/p(x){y是x的素因子}，移项后整理得f(x)=(f(x/y)+p(x))/g(x){y是x的因子}，因为

x/y<x，可以用记忆化搜索的方式计算f(x)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1000005;
const int maxm = 100000;

double f[maxn];
int prime[maxm], cnt, vis[maxn];

void init() {
	memset(vis, 0, sizeof(vis));
	cnt = 0;
	f[0] = f[1] = 1;
	for (ll i = 2; i < maxn; i++) 
		if (!vis[i]) {
			prime[cnt++] = i;
			for (ll j = i*i; j < maxn; j += i)
				vis[j] = 1;
		}
}

double dp(int x) {
	if (x == 1)
		return 0.0;
	if (vis[x])
		return f[x];
	vis[x] = 1;
	double &ans = f[x];
	int g = 0, p = 0;
	ans = 0;
	for (int i = 0; i < cnt && prime[i] <= x; i++) {
		p++;
		if (x % prime[i] == 0) {
			g++;
			ans += dp(x / prime[i]);
		}
	}
	ans = (ans + p) / g;
	return ans;
}

int main() {
	init();
	memset(vis, 0, sizeof(vis));
	int t, n, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		printf("Case %d: %.10f\n", cas++, dp(n));
	}
	return 0;
}

UVA - 11762 Race to 1