zoj 2777 Visible Lattice Points（欧拉函数，基础）

题目

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;

int ans[1100];
int phi[30010],prime[30010],N=30010;
bool is_prime[30010];

void get_phi()  
{  
    int i, j, k;  
    k = 0;  
    //有些题目1的欧拉函数是1，请注意
    //phi[1]=1;
    for(i = 2; i < N; i++)  
    {  
        if(is_prime[i] == false)  
        {  
            prime[k++] = i;  
            phi[i] = i-1;  
        }  
        for(j = 0; j<k && i*prime[j]<N; j++)  
        {  
            is_prime[ i*prime[j] ] = true;  
            if(i%prime[j] == 0)  
            {  
                phi[ i*prime[j] ] = phi[i] * prime[j];  
                break;  
            }  
            else  
            {  
                phi[ i*prime[j] ] = phi[i] * (prime[j]-1);  
            }  
        }  
    }  
}  

int main()
{
    int i,t,n;
    get_phi();
    ans[1]=3;
    for(i=2;i<1010;i++)
    {
        ans[i]=ans[i-1]+phi[i]*2;
    }
    scanf("%d",&t);

    for(i=1;i<=t;i++)
    {
        scanf("%d",&n);
        printf("%d %d %d
",i,n,ans[n]);
    }
    return 0;
}