Send a Table UVA

题意：求1~n中有几对互质的数。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------摘自百度百科

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int maxn=50010;
 9 
10 int n;
11 int p[maxn],sum[maxn];
12 
13 void p_table(){
14     p[1]=0;
15     for(int i=2;i<=maxn;i++) if(!p[i])           //说明i是素数
16     {    for(int j=i;j<=maxn;j+=i){              //刷表，最好用笔模拟一下
17             if(!p[j]) p[j]=j;      
18             p[j]=p[j]/i*(i-1);                   //不能写成 p[j]=p[j]*(i-1)/i，因为可能会超int！！！
19         }
20     }
21     sum[1]=p[1];
22     for(int i=2;i<=maxn;i++) sum[i]=sum[i-1]+p[i];
23 }
24 
25 int main()
26 {   p_table();
27     while(~scanf("%d",&n)&&n) printf("%d
",2*sum[n]+1);
28     return 0;
29 }