这是一个斐波那契的衍生。
a=i-sqrt(i);
b=log(i);
c=sin(i)*sin(i)*i;
可以看到当n稍微大点的时候，那么[1,n]中的值都是你要计算的，而且由于递推函数的特殊，你的代码对在[1,n]内的值重复prime函数多次。造成了时间上不必要的浪费。所以你可以选择用一个数组把计算过的值存起来，下次要用的时候直接下标访问。

如果想练习递归的话，也是要用到数组来存已经计算过的值，先给数组初始化为-1（运用打表的思想，-1表示没计算过，其他表示计算过）。那么下次要计算[1,n]中某个数时，先判断下在那个位置有没有存入你想要的值（也就是数组记录的值是不是-1），如果有就返回数组记录的值，没有才计算。这个可以算作是一个比较简单的记忆化搜索。

那么这个函数可以这样优化下。
const int MAXN = 1e6 + 10;
const int mod = 1000000;
int dp[MAXN];

int prime(int i)
{
if(i==0)
return 1;
if(dp[i] != -1)
return dp[i];
double a,b,c;
a=i-sqrt(i);
b=log(i);
c=sin(i)*sin(i)*i;
dp[i] = prime(a)+prime(b)+prime(c);
return dp[i] % mod;
}

对于结果mod一个数，这是防止结果溢出。
基本定理：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p 　　
(a * b) % p = (a % p * b % p) % p 　　
ab % p = ((a % p)b) % p
这是数论中的知识，我没有怎么学，你有兴趣可以去学下。