线性（欧拉）筛

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 const int maxn = 1e6+5;
 9 bool flag[maxn]; //标记数组
10 ll phi[maxn]; //欧拉函数值
11 int prime[maxn]; //同时得到素数筛
12 int cnt = 0;
13 void Get_phi(int n)
14 {
15     cnt = 0;
16     memset(flag,true,sizeof(flag));
17     phi[1] = 1;
18     for(int i=2;i<=n;i++)
19     {
20         if(flag[i]) //素数
21         {
22             prime[cnt++] = i;
23             phi[i] = i-1; //素数的欧拉函数值是i-1
24         }
25         for(int j=0;j<cnt;j++)
26         {
27             if(i*prime[j]>n)
28             {
29                 break;
30             }
31             flag[i*prime[j]] = false;//素数的倍数不是素数
32             if(i%prime[j]==0) //i%mod prime = 0,那么phi(i*p) = p*phi(i)
33             {
34                 phi[i*prime[j]] = prime[j]*phi[i];
35                 break;
36             }
37             else phi[i*prime[j]] = (prime[j]-1)*phi[i];//i mod prime != 0, 那么 phi(i * prime) == phi(i) * (prime-1)
38         }
39     }
40 }
41 ll sum[maxn];
42 int main()
43 {
44     Get_phi(1e6);
45     for(int i=2;i<=1000;i++)
46     {
47         sum[i] = sum[i-1]+phi[i];
48        // cout<<sum[i]<<endl;
49     }
50     int n;
51     while(cin>>n)
52     {
53         if(n==0) break;
54         cout<<sum[n]<<endl;
55     }
56     return 0;
57 }