hdu 2582 f(n) 数学

打表找规律：

当n为质数是，GCD(n)=n;

当n为质数k的q次方时，GCD(n)=k;

其他情况，GCD(n)=1.

代码如下：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<stdio.h>
 4 #define ll long long
 5 #define M 1000001
 6 using namespace std;
 7 ll a[M];
 8 int prime[79000],cnt;
 9 bool f[M];
10 int fac(int n)
11 {
12     for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++){
13         if(n%prime[i]==0){
14             n/=prime[i];
15             while(n%prime[i]==0) n/=prime[i];
16             if(n==1) return prime[i];
17             return 0;
18         }
19     }
20     return 0;
21 }
22 void init()
23 {
24     int i,j,k;
25     cnt=0;
26     for(i=2;i<M;i++){
27         if(f[i]==0) prime[cnt++]=i;
28         for(j=0;j<cnt&&i*prime[j]<M;j++){
29             f[i*prime[j]]=1;
30             if(i%prime[j]==0) break;
31         }
32     }
33 }
34 int main()
35 {
36     int i,k,n;
37     init();
38     while(scanf("%d",&n)!=EOF){
39         ll ans=0;
40         for(i=3;i<=n;i++){
41             if(f[i]==0) ans+=i;
42             else{
43                 k=fac(i);
44                 if(k) ans+=k;
45                 else ans+=1;
46             }
47         }
48         printf("%I64d
",ans);
49     }
50     return 0;
51 }

View Code