f(n)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 165    Accepted 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 #include #include __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=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 ",sum[n]); } return 0; }
希望大家把我疑问给我解释下