hdu 2583 f(n) 做的迷迷糊糊的一道题

f(n)

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 165Accepted Submission(s): 92

Problem Description

This time I need you to calculate the f(n) . (3<=n<=1000000)

f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n).
Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])
C[n][k] means the number of way to choose k things from n some things.
gcd(a,b) means the greatest common divisor of a and b.

Input

There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF.

Output

For each test case:
The output consists of one line with one integer f(n).

Sample Input

3
26983

Sample Output

3
37556486

现在仍然不是很懂

/*通过打表找GCD的规律，规律如下：
GCD(n)，当n只有一个质因子的时候GCD(n)不会为1。
即质因子数大于等于2 的时候  GCD(n)=1
此时GCD等于n的这个唯一的质因子。
任何一个数都能分解成质因数的次方相乘
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
__int64 prime[100000],c;
__int64 vis[1000000+10];
__int64 sum[1000000+10];
void get_prime()
{
    __int64 i,j,n=1000000,m;
    c=0;
    m=(__int64)sqrt(n+0.5);
    memset(vis,0,sizeof(vis));
    for(i=2;i<=m;i++)
        if(!vis[i])
    {
    
        for(j=i*i;j<=n;j+=i) vis[j]=1;
    }
    for(j=2;j<=n;j++) if(!vis[j])
            prime[c++]=j;
}
__int64 get(__int64 n)
{
    __int64 i,k,cnt=0;
    for(i=0;prime[i]*prime[i]<=n&&i<c;i++)//prime[i]*prime[i] 这里为什么？？？
    {
        if(n%prime[i]==0)
        {
            n=n/prime[i];
            while(n%prime[i]==0)
                n=n/prime[i];
            cnt++;
            k=prime[i];
        }
        if(cnt>=2) return 1;//含有2个质因子 则为1
    }
   if(n>1)   //大于1说明还存在一个质因子  这里说实话我也不懂为什么 
    {   
        cnt++;   
        k=n;   
    }   
    if(cnt>=2)   
        return 1;   
    else  
        return k; 
}
int main()
{
    __int64 i,n;
    sum[3]=3;
    get_prime();
    for(i=4;i<=1000000;i++)
        if(vis[i])//不是质数（素数）
        sum[i]=sum[i-1]+get(i);
        else sum[i]=sum[i-1]+i;//是质数 只有一个质因子 就是其本身
    while(scanf("%I64d",&n)!=EOF)
    {
        printf("%I64d\n",sum[n]);
    }
    return 0;
}

希望大家把我疑问给我解释下