HDU 2582-f(n)(求n个组合数最大公约数的和)

题目地址：HDU 2582
题意：给出公式Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])，让求f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n)。
思路：对于来说,有以下三种
(1)，如果n为素数，那么G=n；
(2)，如果n有多个素因子，那么G=1；
(3)，如果n只有一个素因子，那么G=该素因子。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long  LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-7;
const int Maxn=1e6+10;
bitset<Maxn>pri;
LL prime[Maxn];
int k;
void is_prime()
{
    pri.set();
for(int i=2;i<Maxn;i++){
if(pri[i]){
            prime[k++]=i;
for(int j=i+i;j<Maxn;j+=i)
                pri[j]=0;
        }
    }
}
LL Devide(int n)
{
    LL cnt=0;
int k=n;
int t=(int)sqrt(n*1.0);
for(int i=0;prime[i]<=t;i++){
if(n%prime[i]==0){
            cnt++;
while(n%prime[i]==0)
                n/=prime[i];
            k=prime[i];
        }
if(cnt>1) return 1;
    }
if(n>1){
        cnt++;
        k=n;
    }
if(cnt>1)
return 1;
else
return k;

}
LL f[Maxn];
int main()
{
int n;
    is_prime();
for(int i=3;i<Maxn;i++){
if(pri[i])
            f[i]=f[i-1]+i;
else
            f[i]=f[i-1]+Devide(i);
    }
while(~scanf("%d",&n)){
printf("%lld\n",f[n]);
    }
return 0;
}