学步园

欧拉函数，直接打表

#include<stdio.h>
#include<string.h>
#define N 3000000
int a[N],b[N];
int main()
{
    int i,j,n,m;
    __int64 sum;
    for(i=2;i<N;i++)
        a[i]=i;
    for(i=2;i<N;i++)
    {
        if(b[i]==1)continue;
        a[i]=i-1;
        for(j=i+i;j<N;j=j+i)
        {
            b[j]=1;
         a[j]=a[j]/i*(i-1);
        }
    }
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        sum=0;
        for(i=n;i<=m;i++)
        {
            sum+=a[i];
        }
        printf("%I64d\n",sum);
    }
    return 0;
}